JOI logo
第18回日本情報オリンピック 予選4

2018年12月10日
情報オリンピック日本委員会

問題
  日本沈没 (Japan Sinks) (配点 100点)
  時間制限 : 2sec / メモリ制限 : 256MB

問題文

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

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

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

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

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

制約

入力・出力

入力
入力は以下の形式で標準入力から与えられる.
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

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


入力例 2
6
3 2 3 0 2 0

出力例 2
2

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


入力例 3
10
4 1 2 1 2 3 5 4 3 2

出力例 3
3