B - 山のデータ Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋くんは、東西方向に並んだ地点の高さをまとめたデータを持っている。西から 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