Inadequate Operation#12903

Inadequate Operation

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 .

Input

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

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

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Note

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.