ibasic 不喜歡 Dimigo 所在的廣德山，因此決定繪製一座新的山。

ibasic 繪製的山可以用二維平面上的 $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$，皆滿足 $|h_i - h_{i-1}| = 1$ 的山。

為了將他繪製的山變成「美麗江山」，ibasic 可以對圖形進行以下修改：

• 選擇兩個整數 $l$ 與 $r$（其中 $1 \le l \le r \le N-1$），將 $h_l, h_{l+1}, \ldots, h_{r}$ 的值各加上 $1$。
• 選擇兩個整數 $l$ 與 $r$（其中 $1 \le l \le r \le N-1$），將 $h_l, h_{l+1}, \ldots, h_{r}$ 的值各減去 $1$。

由於修改過程中不能破壞圖形，因此在修改後，所有的 $h_i$ 必須保持大於或等於 $0$。

修改圖形是一項相當麻煩的工作，因此 ibasic 決定將修改次數降至最低。請計算 ibasic 為了將他繪製的山變成「美麗江山」，最少需要進行幾次修改。

輸入格式

第一行輸入一個整數 $N$。$(2 \le N \le 10^6)$

第二行輸入 $N+1$ 個整數 $h_0, h_1, \ldots, h_N$，代表山的高度，以空白分隔。$(0 \le h_i \le 10^9;$ $h_0 = h_N = 0)$

輸出格式

第一行輸出 ibasic 為了將他繪製的山變成「美麗江山」所需的最少修改次數。若無論如何修改都無法將其變成「美麗江山」，則輸出 -1。

範例

範例輸入 1

4
0 3 2 4 0

範例輸出 1

3

範例輸入 2

5
0 3 2 5 9 0

範例輸出 2

-1