King Whomp 走下他的堡垒

King Whomp 正走下 Whomp 堡垒去与马里奥（Mario）战斗。

为了走下去，他必须沿着由 $N$ 级台阶组成的楼梯向下走。每一级后续台阶的高度都小于或等于前一级台阶的高度（以便他能在楼梯尽头找到马里奥）。

然而，King Whomp 最近受伤了，因此他无法走下高度差大于 1 的台阶。因此，他的 Whomp 手下们需要不断调整楼梯：要么从当前台阶上拆除一块砖，使当前台阶的高度降低 1；要么在下一级台阶上增加一块砖，使其高度增加 1，以确保国王陛下的安全。

Whomp 们每增加或拆除一块砖都需要消耗 1 单位的体力。你能帮他们计算出，帮助 King Whomp 安全地从 Whomp 堡垒走到地面（高度为 0，即马里奥所在的位置）所需的最小体力消耗吗？

输入格式

输入的第一行是一个整数 $N$（$1 \le N \le 1\,000\,000$），表示台阶的数量。

输入的第二行包含 $N$ 个空格分隔的整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 1\,000\,000$），表示每级台阶的高度，其中 $a_1 \ge a_2 \ge \dots \ge a_n$。注意，King Whomp 需要从第 $n$ 级台阶走到地面，地面的高度为 0。

输出格式

输出一行，包含一个整数 $E$，表示 Whomp 手下们为了确保 King Whomp 安全走下 Whomp 堡垒所需的最小体力消耗。

样例

样例输入 1

5
9 7 5 4 4

样例输出 1

5

样例输入 2

4
5 4 3 2

样例输出 2

1