E - Min Subtraction
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
長さ 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
- 入力される値はすべて整数.
入力
入力は以下の形式で標準入力から与えられる.
N A_1 A_2 \cdots A_N
出力
答えを出力せよ.
入力例 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