你正在和朋友们一起在运动场上玩跨越障碍物的游戏。游戏从数轴上的位置 $0$ 开始，每个障碍物从左到右依次放置在 $X_1 < X_2 < \cdots < X_N$ 上，其中 $X_1 \ge 1$。

你的目标是跨越数轴上的 $N$ 个障碍物。为此，你可以进行以下两种行动：

• 向右走 $1$ 个单位。也就是说，如果从位置 $x$ 出发，将到达 $x+1$。
• 向右跳 $2$ 个单位。也就是说，如果从位置 $x$ 出发，将到达 $x+2$。

所谓“跨越障碍物”，指的是通过跳跃越过障碍物。换句话说，要跨越位于位置 $X_i$ 的障碍物，必须从位置 $X_i-1$ 向右跳 $2$ 个单位，到达位置 $X_i+1$。

例如，如下图所示，假设在数轴上的位置 $2, 5, 11$ 处放置了障碍物。

可以通过以下方法跨越所有障碍物。下面用 → 表示走路，用 ⟹ 表示跳跃。

• 方法 1：$0 → 1 ⟹ 3 → 4 ⟹ 6 → 7 ⟹ 9 → 10 ⟹ 12$（移动 $8$ 次，跨越 $3$ 个障碍物）
• 方法 2：$0 → 1 ⟹ 3 → 4 ⟹ 6 ⟹ 8 ⟹ 10 ⟹ 12$（移动 $7$ 次，跨越 $3$ 个障碍物）

但是，以下方法无法跨越所有障碍物：

• 方法 3：$0 ⟹ 2 ⟹ 4 ⟹ 6 ⟹ 8 ⟹ 10 ⟹ 12$（移动 $6$ 次，跨越 $2$ 个障碍物）
• 方法 4：$0 → 1 ⟹ 3 ⟹ 5 ⟹ 7 ⟹ 9 → 10 ⟹ 12$（移动 $7$ 次，跨越 $2$ 个障碍物）
• 方法 5：$0 → 1 ⟹ 3 → 4 → 5 ⟹ 7$（移动 $5$ 次，跨越 $1$ 个障碍物）

在每个示例中，移动次数等于走路次数与跳跃次数之和。在这些示例中，方法 2 是以最少移动次数跨越所有障碍物的最优方法。

你希望找到一种移动次数最少、能够跨越所有障碍物的最优方法。但需要注意的是，在仅允许上述两种行动的情况下，也可能存在无法跨越所有障碍物的情形。

限制

• 所有给定的数都是整数。
• $1 \le N \le 250\,000$
• $1 \le X_1 < X_2 < \cdots < X_N \le 250\,000$

子任务

1. （7 分）$N = 1,\ X_1 \le 5$
2. （12 分）$N = 1,\ X_1 \le 5\,000$
3. （23 分）$N \le 5\,000$，且对所有 $1 \le i \le N$，有 $X_i \le 5\,000$
4. （58 分）无额外限制条件

输入格式

第一行给出整数 $N$。

第二行给出 $N$ 个整数 $X_1, X_2, \ldots, X_N$，按顺序用空格分隔。

输出格式

如果无法跨越所有障碍物，输出 $-1$。

如果可以跨越所有障碍物，输出跨越所有障碍物所需的最少移动次数。

样例数据

样例 1

输入：

3
2 5 11

输出：

7

样例 2

输入：

3
7 20 25

输出：

14

样例 3

输入：

4
1 4 5 8

输出：

-1