← 返回题目列表

AtCoder · arc036_b

B. 山地数据

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

問題文

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) 满足有关山东侧的条件。
上面设置的整数 (3, 5, 6) 是尺寸 代表一座 6 - 3 + 1 = 4 山。尺寸 没有比 5 更大的山脉,所以4 是正确答案。


入力例2

7
90
70
50
30
20
10
5

出力例2

7