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