あなたは友達と一緒に運動場で障害物を越えるゲームをしています。ゲームは数直線上の位置 $0$ から始まり、各障害物は左から右へ順に $X_1 < X_2 < \cdots < X_N$ の位置に配置されています。ただし、$X_1 \ge 1$ です。

あなたの目標は、数直線上にある $N$ 個の障害物をすべて越えることです。そのために、次の 2 種類の行動を行うことができます。

• 右に $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 がすべての障害物を最小の移動回数で越える最適な方法です。

あなたは、すべての障害物を越えることができ、かつ移動回数が最小となる最適な方法を求めたいと考えています。ただし、上記の 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 点）追加の制約なし

入力

1 行目に整数 $N$ が与えられる。

2 行目に $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