You are given an array of nonnegative integers. In one operation, you can choose any such that 1\le i \le n-1 and \max(a_i, a_{i+1})>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 . It can be proven that it's always possible to make all numbers equal to .
The first line of the input contains a single integer (2 \le n \le 200\:000) — the number of integers.
The second line of the input contains integers a_1, a_2, \ldots, a_n (0 \le a_i \le 10^9) — the elements of the array.
Output a single integer — the smallest number of operations required to make all elements equal to .
Example 1
Example 2
Example 3
In the first test case, you can apply this operation times to i = 1, and then times to i = 2.
In the second test case, you can apply this operation times to i = 1.