日本沈没 (Japan Sinks)

日本列島は細長い列島である．日本列島は平行な境界線により \(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\) 点) 追加の制約はない．

JOI 2019 · JCIOI · CC BY-SA 4.0