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