問題文

Vil 君の家には壊れたタンスがあります。このタンスはどの段も一度引き出した後は引っ込めることができないため、 引き出した段の一つ下の段から物を取り出すことが出来なくなります(引き出した段が最下段である場合はこの限りではありません)。

タンスは下から順に番号の付いた合計 $N$ 段からなり、$i$ 段目の引き出しには整数 $A_i$ が入っています( $A_i$ はすべて異なる)。 このタンスの $B_1,B_2,\dots ,B_M$ 段目からこの順に整数を取り出し、それらを取り出した順に並べることで長さ $M$ の単調増加列を作ることを考えます。 このとき、以下の条件を満たす必要があります。

• 問題文中の $B$ について $B_i-1=B_j$ を満たす $(i,j)(i<j)$ は存在しない。

以上の条件を満たす単調増加列のうち最長のものの長さを求めてください。

入力

$N$
$A_1{A}_2\dots A_N$

• 入力はすべて整数
• $1\le N\le 2\times {10}^5$
• $1\le A_i\le N$
• $i\ne j$ であれば $A_i\ne A_j$

出力

問題文中の条件を満たす単調増加列のうち最長のものの長さを出力し、最後に改行してください。

サンプル

5
2 3 4 1 5

4

8
4 3 5 1 7 6 2 8

5

15
12 5 15 3 11 8 14 13 6 10 9 7 4 2 1

8