問題文

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

・ レベル $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)$
入力は全て整数

出力

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

サンプル

3
1 3 2

1

1
1

0

6
5 3 1 2 4 2

2