You and your friends playing a hurdle-jumping game on a number line. The game starts at position $0$. There are $N$ hurdles placed from left to right at positions $X_1 < X_2 < \cdots < X_N$, where $X_1 \ge 1$.

Your goal is to clear all $N$ hurdles on the number line. To do so, you may perform the following two actions:

• Walk $1$ unit to the right. That is, if you start from position $x$, you arrive at $x+1$.
• Jump $2$ units to the right. That is, if you start from position $x$, you arrive at $x+2$.

To “clear a hurdle” means to jump over it. In other words, to clear the hurdle at position $X_i$, you must jump $2$ units to the right from position $X_i-1$, arriving at position $X_i+1$.

For example, in the figure below, suppose hurdles are placed at positions $2, 5, 11$ on the number line.

You can clear all hurdles in the following ways. Below, → denotes walking, and ⟹ denotes jumping.

• Method 1: $0 → 1 ⟹ 3 → 4 ⟹ 6 → 7 ⟹ 9 → 10 ⟹ 12$ (8 moves, clears 3 hurdles)

However, the following methods cannot clear all hurdles:

• Method 3: $0 ⟹ 2 ⟹ 4 ⟹ 6 ⟹ 8 ⟹ 10 ⟹ 12$ (6 moves, clears 2 hurdles)

In each example, the number of moves equals the number of walks plus the number of jumps. Among these examples, Method 2 is optimal: it clears all hurdles with the minimum number of moves.

You want to find an optimal way that clears all hurdles using the minimum number of moves. However, note that under the restriction that only the two actions above are allowed, it may be impossible to clear all hurdles.

Constraints

• All given numbers are integers.
• $1 \le N \le 250,000$
• $1 \le X_1 < X_2 < \cdots < X_N \le 250,000$

Scoring

1. (7 points) $N = 1,\ X_1 \le 5$
2. (12 points) $N = 1,\ X_1 \le 5,000$
3. (23 points) $N \le 5,000$, and for all $1 \le i \le N$, $X_i \le 5,000$
4. (58 points) No additional constraints

Input Format

The first line contains an integer $N$.

The second line contains $N$ integers $X_1, X_2, \ldots, X_N$, separated by spaces in order.

Output Format

If it is impossible to clear all hurdles, output $-1$.

If it is possible to clear all hurdles, output the minimum number of moves required to clear all hurdles.

Example

Example 1

Input:

3
2 5 11

Output:

7

Example 2

Input:

3
7 20 25

Output:

14

Example 3

Input:

4
1 4 5 8

Output:

-1