問題文

長さ N の非負整数列 A=(A_1,A_2,\cdots,A_N) が与えられます．

あなたは以下の操作を好きな回数 (0 回でもよい) 繰り返すことができます．

• 整数 i (1 \leq i \leq N-1) を選ぶ． v=\min(A_i,A_{i+1}) とする．A_i の値を A_i-v で置き換え，A_{i+1} の値を A_{i+1}-v で置き換える．

操作後の A に含まれる 0 の個数の最大値を求めて下さい．

制約

• 2 \leq N \leq 250000
• 1 \leq A_i \leq 10^9
• 入力される値はすべて整数．

入力例 1

4
1 2 1 2

出力例 1

3

次のように操作を行えばよいです．

• i=1 で操作し，A=(0,1,1,2) になる．
• i=2 で操作し，A=(0,0,0,2) になる．

このとき，A は 3 個の 0 を含みます． A が 4 個の 0 を含むようにすることはできないので，3 が答えになります．

入力例 2

5
1 1 1 1 1

出力例 2

4

入力例 3

6
6 5 4 3 2 1

出力例 3

5

入力例 4

20
786820955 250480341 710671229 946667801 19271059 404902145 251317818 22712439 520643153 344670307 274195604 561032101 140039457 543856068 521915711 857077284 499774361 419370025 744280520 249168130

出力例 4

13