给你一个由 $n$ 个非负整数组成的数组 $a$。在一次操作中，你可以选择任意满足 $1 \le i \le n - 1$ 且 $\max(a_i, a_{i+1}) > 0$ 的 $i$，并将 $a_i$ 和 $a_{i+1}$ 都替换为 $\max(a_i, a_{i+1}) - 1$。

求将所有元素都变为 0 所需的最少操作次数。可以证明，总是可以使所有数字都变为 0。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 200\,000$) — 整数的个数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — 数组的元素。

输出格式

输出一个整数 — 将所有元素都变为 0 所需的最少操作次数。

样例

输入样例 1

3
2 0 22

输出样例 1

24

输入样例 2

3
0 2022 0

输出样例 2

2022

输入样例 3

6
30 20 10 10 20 30

输出样例 3

70

说明

在第一个样例中，你可以对 $i = 1$ 执行 2 次该操作，然后对 $i = 2$ 执行 22 次该操作。

在第二个样例中，你可以对 $i = 1$ 执行 2022 次该操作。