AT_agc040_e [AGC040E] Prefix Suffix Addition

すぬけくん有一个长度为 $N$ 的整数序列 $x_1,x_2,\cdots,x_N$。最初，$x$ 的所有元素都是 $0$。 すぬけくん可以以任意顺序、任意次数进行以下两种操作： - 操作 $1$：任选一个整数 $k$（$1 \leq k \leq N$），以及一个长度为 $k$ 的非负整数序列 $c_1,c_2,\cdots,c_k$，其中 $c$ 必须是**广义单调递增**的。然后，对于所有 $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$，其中 $c$ 必须是**广义单调递减**的。然后，对于所有 $i$（$1 \leq i \leq k$），将 $x_{N-k+i}$ 替换为 $x_{N-k+i} + c_i$。 すぬけくん的目标是使得对于所有 $i$，都有 $x_i = A_i$。请你求出他为了达成目标所需操作次数的最小值。

输入以如下格式从标准输入读入： > $N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出すぬけくん为达成目标所需的最小操作次数。

## 限制条件 - $1 \leq N \leq 2 \times 10^5$ - $1 \leq A_i \leq 10^9$ - 输入的所有值均为整数。 ## 样例解释 1 例如，可以通过如下 $3$ 次操作达成目标，且少于 $3$ 次无法达成： - 令 $k=2, c=(1,2)$，执行操作 $1$。操作后，$x=(1,2,0,0,0)$。 - 令 $k=3, c=(0,0,1)$，执行操作 $1$。操作后，$x=(1,2,1,0,0)$。 - 令 $k=2, c=(2,1)$，执行操作 $2$。操作后，$x=(1,2,1,2,1)$。 由 ChatGPT 4.1 翻译