問題文
Takahashi-kun 拥有总结东西方向排列点高度的数据。从西边来 i (1 ≦ i ≦ N) 点的高度是 h_i 。该数据中没有相同高度的点。
高桥君决定将数据的“山”和“山大小”定义如下。
3 整数集 对于 (s,t,u) (1 ≦ s ≦ t ≦ u ≦ N) ,如果满足以下条件,则该集合代表一座山。
- 山西侧情况: s ≦ i ≦ t-1 的任意整数 对于 i ,h_i < h_{i+1}成立。
- 山东侧情况: t ≦ i ≦ u-1 的任意整数 对于 i ,h_i > h_{i+1}成立。
满足这些条件的一组整数 关于 (s,t,u) ,山的大小是 在u-s+1 中定义。
高桥君决定调查数据中山脉的最大尺寸。
编写一个程序来查找山的最大可能尺寸。
入力
输入是按以下格式从标准输入给出的。
N h_1 h_2 : h_N
- 1 行包含一个表示数据元素数量的整数。 N (1 ≦ N ≦ 3×10^5) 。
- 2 在 N 行给出一个表示点高度的整数。 在行N 行 i 中,一个整数 如果正确答案是满足 h_i (1 ≦ h_i ≦ 10^9) 。
- 1 ≦ i < j ≦ N 的任意整数 对于 i,j ,h_i ≠ h_j 。
部分点
针对此问题设置了部分分数。
- N ≦ 20 的数据集,30 点。
- 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 70 点。
出力
山的最大可能尺寸是 1 行输出。在输出末尾添加换行符。
入力例1
6 4 5 1 6 9 7
出力例1
4
山地数据是[4, 5, 1, 6, 9, 7]。其中,整数集 考虑到 (3, 5, 6) ,
- 1(=h_3) < 6(=h_4) < 9(=h_5) 满足山西侧的条件。
- 9(=h_5) > 7(=h_6) 满足有关山东侧的条件。
入力例2
7 90 70 50 30 20 10 5
出力例2
7