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$ 必须保持非负。

修改图形是一项相当麻烦的工作，因此 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