問題
長さ$ \ N \ $の数列$ \ A = (A_1,A_2,\ldots,A_N) \ $が与えられます。
次の条件を満たす数列$ \ B = (B_1,B_2,\ldots,B_M) \ $の長さ$ \ M \ (1 \leq M \leq N) \ $の最大値を求めて下さい。
- $B \ $は$ \ A \ $の空でない部分列である。（これは連続した部分列でなくてもよい）
-
$ \ B_1 \lt B_2 \lt \ldots \lt B_K \gt B_{K+1} \ldots \gt B_M \ $となる正整数$ \ K \ $が存在する。
例として、$(1,3,4,1)$,$(3,2,1)$,$(1,2,3)$,$(5) \ $などが条件を満たす。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $A_1 \ A_2 \ldots \ A_N$
出力
整数$ \ M \ $の最大値を出力せよ。
出力の末尾には改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)$
- 入力は全て整数である。
入出力例
入力例1
5 1 3 5 2 4
出力例1
4
例えば$ \ B = (1,3,5,4) \ $とすればよい。
入力例2
9 2 5 6 4 3 2 7 8 1
出力例2
7