配点 : 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