問題文
日本列島は細長い列島である．日本列島は平行な境界線により 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
海面の上昇により，日本列島は少しずつ沈没している．現在の海面の高さは 0 であるが，これは時間が経つにつれて徐々に上がり，ついには日本全体が海になってしまう．
JOI 君は，海面の高さが上昇すると，日本の島の数が増減することに気付いた．現在から，日本に陸地がなくなるまでの間 (現在も含む) における，島の数の最大値を求めたい．
制約
- 1 ≦ N ≦ 100000 (= 10^5)
- 0 ≦ A_i ≦ 1000000000 (= 10^9) (1 ≦ i ≦ N)
入力・出力
入力
入力は以下の形式で標準入力から与えられる．
N
A_1 A_2 ... A_N
出力
現在から，日本に陸地がなくなるまでの間 (現在も含む) における，島の数の最大値を 1 行で出力せよ．
小課題
- (7 点) N ≦ 2000, A_i ≦ 2000 (1 ≦ i ≦ N)
- (8 点) N ≦ 2000
- (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