ibasic does not like Gwangdeoksan, the mountain where Dimigo is located, so he decided to draw a new mountain.

The mountain drawn by ibasic can be represented by $N+1$ points $(0, h_0), (1, h_1), \ldots, (N, h_N)$ on a 2D plane. All $h_i$ are non-negative integers, and $h_0 = h_N = 0$.

ibasic wants to make his mountain a beautiful landscape. A beautiful landscape is a mountain where $|h_i - h_{i-1}| = 1$ for all $1 \le i \le N$.

To make his mountain a beautiful landscape, ibasic can modify his drawing as follows:

• Choose two integers $l$ and $r$ such that $1 \le l \le r \le N-1$, and add $1$ to $h_l, h_{l+1}, \ldots, h_{r}$.
• Choose two integers $l$ and $r$ such that $1 \le l \le r \le N-1$, and subtract $1$ from $h_l, h_{l+1}, \ldots, h_{r}$.

Since the drawing must not be ruined, all $h_i$ must remain non-negative after any modification.

Modifying the drawing is quite a tedious task, so ibasic decided to minimize the number of modifications. Find the minimum number of modifications required to make the mountain drawn by ibasic a beautiful landscape.

Input

The first line contains an integer $N$. $(2 \le N \le 10^6)$

The second line contains $N+1$ integers $h_0, h_1, \ldots, h_N$ representing the mountain, separated by spaces. $(0 \le h_i \le 10^9;$ $h_0 = h_N = 0)$

Output

The first line should output the minimum number of modifications required to make the mountain drawn by ibasic a beautiful landscape. If it is impossible to make the mountain a beautiful landscape regardless of the modifications, output -1 instead.

Examples

Input 1

4
0 3 2 4 0

Output 1

3

Input 2

5
0 3 2 5 9 0

Output 2

-1