← 返回题目列表

AtCoder · jsc2023_final_e

E. 最小减法

中文机器翻译题面 查看原题

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