D - 日本沈没 (Japan Sinks)

Time Limit: 2 sec / Memory Limit: 256 MB

配点: 100

問題文

日本列島は細長い列島である.日本列島は平行な境界線により N 個の区画に分けられている.区画には端から順に 1 から N の番号が付けられている.区画 i (1 ≦ i ≦ N) の高さは A_i である.

日本列島は海に囲まれており,海面の高さは場所によらず一定である.高さが海面の高さより高い区画を陸地と呼ぶ.

陸地が連続している部分のことをと呼ぶ.より正確に書くと以下の通りである.整数 l, r (1 ≦ l ≦ r ≦ N) について,日本列島のうち区画 l,区画 l+1...,区画 r からなる部分を領域 [l, r] という.以下の条件を満たす領域 [l, r] を島という:

  • 区画 l,区画 l+1...,区画 r はすべて陸地である.
  • l>1 ならば区画 l-1 は陸地ではない.
  • r<N ならば区画 r+1 は陸地ではない.

海面の上昇により,日本列島は少しずつ沈没している.現在の海面の高さは 0 であるが,これは時間が経つにつれて徐々に上がり,ついには日本全体が海になってしまう.

JOI 君は,海面の高さが上昇すると,日本の島の数が増減することに気付いた.現在から,日本に陸地がなくなるまでの間 (現在も含む) における,島の数の最大値を求めたい.

制約

  • 1 ≦ N ≦ 100000 (= 10^5)
  • 0 ≦ A_i ≦ 1000000000 (= 10^9) (1 ≦ i ≦ N)

入力

入力は以下の形式で標準入力から与えられる.

N
A_1 A_2 ... A_N

出力

現在から,日本に陸地がなくなるまでの間 (現在も含む) における,島の数の最大値を 1 行で出力せよ.

小課題

  1. (7 点) N ≦ 2000, A_i ≦ 2000 (1 ≦ i ≦ N)
  2. (8 点) N ≦ 2000
  3. (85 点) 追加の制約はない.

入力例 1

6
0 1 2 1 3 2

出力例 1

2
  • 海面の高さが 0 以上 1 未満のとき,区画 2, 3, 4, 5, 6 が陸地である.領域 [2, 6] が唯一の島なので,島の数は 1 である.
  • 海面の高さが 1 以上 2 未満のとき,区画 3, 5, 6 が陸地である.領域 [3, 3] と領域 [5, 6] が島なので,島の数は 2 である.
  • 海面の高さが 2 以上 3 未満のとき,区画 5 のみが陸地である.領域 [5, 5] が唯一の島なので,島の数は 1 である.
  • 海面の高さが 3 になると,陸地はなくなり,島の数は 0 になる.

よって島の数の最大値は 2 なので,2 を出力する.


入力例 2

6
3 2 3 0 2 0

出力例 2

2
  • 海面の高さが 0 以上 2 未満のとき,区画 1, 2, 3, 5 が陸地である.領域 [1, 3] と領域 [5, 5] が島なので,島の数は 2 である.
  • 海面の高さが 2 以上 3 未満のとき,区画 1, 3 が陸地である.領域 [1, 1] と領域 [3, 3] が島なので,島の数は 2 である.
  • 海面の高さが 3 になると,陸地はなくなり,島の数は 0 になる.

よって島の数の最大値は 2 なので,2 を出力する.


入力例 3

10
4 1 2 1 2 3 5 4 3 2

出力例 3

3