No.127 門松もどき

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 33
作問者 : krotonkroton

4 ProblemId : 293 / 出題時の順位表

問題文

竹林とは、竹の長さを表す正の整数列 \(A_{1}, A_{2} \ldots A_{N}\) のことである。
門松もどきとは、\(1 \leq i_{1} < i_{2} < \ldots < i_{M} \leq N\) を満たす竹林の部分列 \(A_{i_{1}}, A_{i_{2}} \ldots A_{i_{M}}\) で
\(A_{i_{1}} < A_{i_{M}} < A_{i_{2}} < A_{i_{M-1}} < A_{i_{3}} \ldots\) もしくは \(A_{i_{M}} < A_{i_{1}} < A_{i_{M-1}} < A_{i_{2}} < A_{i_{M-2}} \ldots\) を満たすものをいう。

最長の門松もどきの長さを答えよ。

例: 長さ6の門松もどき

入力

\(N\)
\(A_{1}\) \(A_{2}\) \(\ldots\) \(A_{N}\)

入力はすべて整数で与えられる。

  • \(1 \leq N \leq 3000\)
  • \(1 \leq A_{i} \leq 100000\)

出力

最長の門松もどきの長さを出力してください。

サンプル

サンプル1
入力
6
1 4 7 10 6 2
出力
6
サンプル2
入力
7
1 4 7 3 10 6 2
出力
6

門松もどきは「部分列」であることに注意してください

サンプル3
入力
10
5 9 5 11 20 5 12 17 6 18
出力
5
サンプル4
入力
2
5 5
出力
1

1本でも門松もどきなのだ

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。