問題一覧 > 通常問題

No.1188 レベルX門松列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 137
作問者 : seven_threeseven_three / テスター : ThistleThistle
5 ProblemId : 4880 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-08-22 10:50:20

問題文

門松列とそのレベルを次のように定義します。

・ レベル X の門松列は、2X+1 要素からなる数列である。
・ 要素をそれぞれ B1,B2,...B2X+1 と表すとき、
 B1 > B2 > ... BX > BX+1 < BX+2 ... < B2X < B2X+1 または B1 < B2 < ... BX < BX+1 > BX+2 ... > B2X > B2X+1

N 要素からなる数列 A1,A2,...AN が与えられます。
この数列の部分列で門松列であるもののうち、最もレベルが高いもののレベルを求めてください。
ただし数列の部分列とは、数列の要素を0個以上選んで削除し、残った物を最初の順序を保って並べた数列を表します。

入力

N
A1 A2 ... AN

1 N 105
1 Ai 109 (1iN)
入力は全て整数

出力

最後に改行してください。

サンプル

サンプル1
入力
3
1 3 2
出力
1

最もレベルが高い数列 A の部分列である門松列は {1,3,2} であり、そのレベルは 1 です。

サンプル2
入力
1
1
出力
0

最もレベルが高い数列 A の部分列である門松列は {1} であり、そのレベルは 0 です。

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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。