题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

你正在和朋友们一起在操场上玩跳跃障碍物的游戏。游戏从数轴上的位置 0 开始，各个障碍物从左到右依次放置在 $X_1 < X_2 < ... < 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 处放置有障碍物。

可以通过以下几种方法跳过所有障碍物。下文中，$\rightarrow$ 表示行走，$\implies$ 表示跳跃。

• 方法 1: $0 \rightarrow 1 \implies 3 \rightarrow 4 \implies 6 \rightarrow 7 \implies 9 \rightarrow 10 \implies 12$ (共移动 8 次，跳过 3 个障碍物)

• 方法 2: $0 \rightarrow 1 \implies 3 \rightarrow 4 \implies 6 \implies 8 \implies 10 \implies 12$ (共移动 7 次，跳过 3 个障碍物) 但是，使用以下方法则无法跳过所有障碍物。

• 方法 3: $0 \implies 2 \implies 4 \implies 6 \implies 8 \implies 10 \implies 12$ (共移动 6 次，跳过 2 个障碍物)

• 方法 4: $0 \rightarrow 1 \implies 3 \implies 5 \implies 7 \implies 9 \rightarrow 10 \implies 12$ (共移动 7 次，跳过 2 个障碍物)

• 方法 5: $0 \rightarrow 1 \implies 3 \rightarrow 4 \rightarrow 5$ (共移动 5 次，跳过 1 个障碍物)

在各个示例中，移动次数是行走次数和跳跃次数的总和。在这个示例中，方法 2 是用最少移动次数跳过所有障碍物的最佳方法。

你需要找到一种将移动次数最小化、能够跳过所有障碍物的最佳方法。但是，也可能存在仅用给定的两种行动无法跳过所有障碍物的情况。

输入格式

第一行给定 $N$。

第二行依次给定 $N$ 个整数 $X_1, X_2, \dots, X_N$，由空格分隔。

输出格式

如果无法跳过所有障碍物，则输出 -1。

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

3
2 5 11

7

3
7 20 25

14

4
1 4 5 8

-1

提示

限制条件

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

子任务

1. (7 分) $N = 1, X_1 \le 5$
2. (12 分) $N = 1, X_1 \le 5\,000$
3. (23 分) 对于所有满足 $1 \le i \le N$ 的 $i$，$N \le 5\,000$ 且 $X_i \le 5\,000$
4. (58 分) 无额外限制条件。