分数: 1400 点
问题陈述
Snuke 有一系列 N 整数 x_1,x_2,\cdots,x_N。 最初,所有元素都是 0.
他可以以任意顺序执行任意次数的以下两种操作:
- 操作 1:选择一个整数 k (1 \leq k \leq N)和 非递减 序列 k 非负整数 c_1,c_2,\cdots,c_k。 然后,对于每个 i (1 \leq i \leq k),替换 x_i 与 x_i+c_i.
- 操作 2:选择一个整数 k (1 \leq k \leq N)和 非增加 序列 k 非负整数 c_1,c_2,\cdots,c_k。 然后,对于每个 i (1 \leq i \leq k),替换 x_{N-k+i} 与 x_{N-k+i}+c_i.
他的目标是 x_i=A_i 对于所有人 i。 找出实现该目标所需的最少操作数。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N
输出
打印实现 Snuke 目标所需的最少操作数。
示例输入 1
5 1 2 1 2 1
示例输出 1
3
下面显示了通过三个操作实现该目标的一种方法。 少于三次行动就无法实现这一目标。
- 进行操作 1 并选择 k=2,c=(1,2)。现在我们有 x=(1,2,0,0,0).
- 进行操作 1 并选择 k=3,c=(0,0,1)。现在我们有 x=(1,2,1,0,0).
- 进行操作 2 并选择 k=2,c=(2,1)。现在我们有 x=(1,2,1,2,1).
示例输入 2
5 2 1 2 1 2
示例输出 2
2
示例输入 3
15 541962451 761940280 182215520 378290929 211514670 802103642 28942109 641621418 380343684 526398645 81993818 14709769 139483158 444795625 40343083
示例输出 3
7