問題一覧 > 通常問題

No.1188 レベルX門松列

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

問題文

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

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

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

入力

$N$
$A_{1}\ A_{2}\ ...\ A_{N}$

$1$ $≤$ $N$ $≤$ $10^5$
$1$ $≤$ $A_{i}$ $≤$ $10^9$ $(1≤i≤N)$
入力は全て整数

出力

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

サンプル

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。