← 返回题目列表

AtCoder · typical90_bh

060. 奇美拉(★5)

中文机器翻译题面 查看原题

配点: 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