AT_npcapc_2024_k Peace with Magic

NPCA 国由 $N$ 个横向排成一列的格子组成，每个格子从左到右依次编号为 $1$ 到 $N$。格子 $i$ 的高度记作 $H_i$。初始时，$H_1=H_2=\dots=H_N=0$。 对于每个 $1\leq i\leq N-1$，当 $H_i$ 与 $H_{i+1}$ 的差的绝对值小于 $D_i$ 时，格子 $i$ 与格子 $i+1$ 之间就会发生争斗。NPCA 国热爱和平，其国王纳普卡的目标是让所有相邻的格子之间都不会发生争斗。为此，纳普卡可以使用如下魔法任意次（包括零次）： - 选择满足 $H_i=H_{i+1}=\dots=H_j$ 的一组整数 $i,j$（$1\leq i\leq j\leq N$），并将 $H_i,H_{i+1},\dots,H_j$ 的每一个都加 $1$。 请你计算，为了达成目标，纳普卡最少需要施放多少次魔法。

输入由标准输入给出。 > $N$ $D_1$ $D_2$ $\dots$ $D_{N-1}$

输出答案。

## 样例解释 1 初始时，$(H_1,H_2,H_3,H_4)=(0,0,0,0)$。例如，可以按如下方法施放魔法： - 选择 $(i,j)=(1,3)$，得到 $(H_1,H_2,H_3,H_4)=(1,1,1,0)$。 - 选择 $(i,j)=(1,2)$，得到 $(H_1,H_2,H_3,H_4)=(2,2,1,0)$。 - 选择 $(i,j)=(2,2)$，得到 $(H_1,H_2,H_3,H_4)=(2,3,1,0)$。 - 选择 $(i,j)=(2,2)$，得到 $(H_1,H_2,H_3,H_4)=(2,4,1,0)$。 实现目标时共施放了 $4$ 次魔法，且这是最少次数。注意，可以选择 $i=j$ 的区间。 # 数据范围 - $2 \leq N \leq 100$ - $0 \leq D_i \leq 1000$ 由 ChatGPT 5 翻译