配点: 5 点
問題文
长度
小于或等于 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
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N A_1 A_2 \cdots A_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