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 翻译