I. Inadequate Operation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ nonnegative integers. In one operation, you can choose any $$$i$$$ such that $$$1\le i \le n-1$$$ and $$$\max(a_i, a_{i+1}) \gt 0$$$, and replace both $$$a_i$$$ and $$$a_{i+1}$$$ by $$$\max(a_i, a_{i+1}) - 1$$$.

Find the smallest number of operations required to make all elements equal to $$$0$$$. It can be proven that it's always possible to make all numbers equal to $$$0$$$.

Input

The first line of the input contains a single integer $$$n$$$ ($$$2 \le n \le 200\:000$$$) — the number of integers.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$)  — the elements of the array.

Output

Output a single integer — the smallest number of operations required to make all elements equal to $$$0$$$.

Examples
Input
3
2 0 22
Output
24
Input
3
0 2022 0
Output
2022
Input
6
30 20 10 10 20 30
Output
70
Note

In the first test case, you can apply this operation $$$2$$$ times to $$$i = 1$$$, and then $$$22$$$ times to $$$i = 2$$$.

In the second test case, you can apply this operation $$$2022$$$ times to $$$i = 1$$$.