ibasicは、Dimigoの敷地である光徳山が気に入らず、新しい山を描くことにした。

ibasicが描いた山は、2次元平面上の $N+1$ 個の点 $(0, h_0), (1, h_1), \ldots, (N, h_N)$ で表すことができる。すべての $h_i$ は非負の整数であり、$h_0 = h_N = 0$ である。

ibasicは、自分が描いた山を「美しい江山」にしたいと考えている。「美しい江山」とは、$1 \le i \le N$ を満たすすべての $i$ について $|h_i - h_{i-1}| = 1$ が成り立つ山のことである。

ibasicは、自分が描いた山を「美しい江山」にするために、図を次のように修正することができる。

• $1 \le l \le r \le N-1$ である2つの整数 $l, r$ を選び、$h_l, h_{l+1}, \ldots, h_{r}$ に $1$ を加える。
• $1 \le l \le r \le N-1$ である2つの整数 $l, r$ を選び、$h_l, h_{l+1}, \ldots, h_{r}$ から $1$ を引く。

図を修正する過程で図が壊れてはならないため、修正後もすべての $h_i$ は $0$ 以上でなければならない。

図を修正するのは非常に面倒な作業であるため、ibasicは修正回数を最小限に抑えることにした。ibasicが描いた山を「美しい江山」にするために必要な最小の修正回数を求めよ。

入力

1行目に整数 $N$ が与えられる。$(2 \le N \le 10^6)$

2行目に山を表す $N+1$ 個の整数 $h_0, h_1, \ldots, h_N$ が空白区切りで与えられる。$(0 \le h_i \le 10^9; h_0 = h_N = 0)$

出力

1行目に、ibasicが描いた山を「美しい江山」にするために必要な最小の修正回数を出力せよ。ただし、どのように修正しても「美しい江山」にすることができない場合は、代わりに -1 を出力せよ。

入出力例

入力 1

4
0 3 2 4 0

出力 1

3

入力 2

5
0 3 2 5 9 0

出力 2

-1