問題文

長さ N の数列 A = (A_1,A_2, \cdots , A_N) が与えられます。
A の（連続とは限らない）部分列 B=(B_1,B_2, \cdots , B_M) であって、次の条件を満たすものを考えます。

条件　ある整数 K(1 \leq K \leq M) が存在して、以下の条件をともに満たす

• 1 \leq j \lt K を満たす全ての j に対し、B_j \lt B_{j+1} が成立する
• K \leq j \lt M を満たす全ての j に対し、B_j \gt B_{j+1} が成立する

B の要素数 M として考えられる最大値を求めてください。

制約

• 1 \leq N \leq 300000
• 1 \leq A_i \leq N
• 入力は全て整数

入力例 1

6
1 2 3 3 2 1

出力例 1

5

A_1,A_2,A_3,A_5,A_6 から B を得ると B = (1,2,3,2,1) となります。
これは K=3 とすると条件を満たす部分列であり、要素数は 5 です。
これよりも要素数の多い部分列であって条件を満たすものは存在しないため、答えは 5 になります。

入力例 2

4
1 2 3 4

出力例 2

4

入力例 3

5
3 3 3 3 3

出力例 3

1