NPCA 国家由 $N$ 个排成一行的方格组成，从左到右编号为 $1$ 到 $N$。设第 $i$ 个方格的高度为 $H_i$。初始时，$H_1 = H_2 = \dots = H_N = 0$。

对于每个 $1 \le i \le N - 1$，如果 $H_i$ 和 $H_{i+1}$ 的绝对差小于 $D_i$，则方格 $i$ 和方格 $i+1$ 之间会产生冲突。NPCA 国家的和平之王 Napuka-kun 旨在消除每一对相邻方格之间的所有冲突。为了实现这一目标，Napuka-kun 可以执行任意次数（包括零次）以下魔法：

• 选择整数 $i$ 和 $j$，满足 $1 \le i \le j \le N$ 且 $H_i = H_{i+1} = \dots = H_j$，然后将 $H_i, H_{i+1}, \dots, H_j$ 每个都加 $1$。

确定 Napuka-kun 为实现其目标所需执行魔法的最小次数。

数据范围

• $2 \le N \le 100$
• $0 \le D_i \le 1000$

输入格式

输入通过标准输入按以下格式给出：

$N$ $D_1 \ D_2 \ \dots \ D_{N-1}$

输出格式

输出答案。

样例

样例输入 1

4
2 3 1

样例输出 1

4

样例输入 2

3
0 0

样例输出 2

0

样例输入 3

10
1 9 5 6 2 7 1 4 8

样例输出 3

22

说明

对于第一个样例： 初始时，$(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)$。

Napuka-kun 总共施展了 4 次魔法以达到目标，这是最少的施展次数。注意你可以选择 $i = j$。