← 返回题目列表

AtCoder · bcu30_2019_b

B. 间隔加法

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

配点 : 100 点

問題文

Milkushii公司的员工青木先生有 N 由元素组成的数列 A 并且,最初数列的所有元素都是 0 。

青木先生希望对以下操作 0 次以上重复执行,使得所有 1 \leq i \leq N 的数列的 i 第几个元素 a_i 变为所需的值。

  • 1 \leq k \leq N 和 1 \leq l \leq N+1-k 满足的正整数 k, l 决定。长度为 k 的非负整数序列 (0 \leq )B_1 \leq B_2 \leq ... \leq B_k 可自由决定,1 \leq i \leq k 针对 A_{l+i-1} := A_{l+i-1} + B_i 。

每次操作都可以使用不同的 k, l, B 。请求出青木先生为了得到目标数列,最少需要进行多少次操作。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq a_i \leq 10^9
  • 输入均为整数

入力

输入将以以下格式从标准输入提供。

N
a_1 a_2 ... a_N

出力

输出青木先生为了得到目标数列所需操作次数的最小值。


入力例 1

2
3 4

出力例 1

1

k = 2, l = 1, B = \{3, 4\} ,那么青木先生可以 1 通过第 n 次操作可以得到目标数列。


入力例 2

2
4 3

出力例 2

2

1 在第 n 次操作中 k = 2, l = 1, B = \{3, 3\} 如果这样做 A 表示 \{3, 3\} 。

2 在第 n 次操作中 k = 1, l = 1, B = \{1\} 如果这样做 A 表示 \{4, 3\} 。

因此青木先生 2 通过第 n 次操作可以得到目标数列,而且 1 由于不可能在 n 次以下操作中得到目标数列, 2 请输出这个。


入力例 3

4
4 0 4 0

出力例 3

2