← 返回题目列表

AtCoder · agc040_e

E. 前缀后缀添加

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

分数: 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