60007 장애물 Silver V

문제

당신은 친구들과 함께 운동장에서 장애물 뛰기 놀이를 하고 있다. 놀이는 수직선 위의 위치 $0$에서 시작하며, 각 장애물은 왼쪽부터 차례로 $X_1 < X_2 < \dots < X_N$ 에 놓여 있다. $X_1 ≥ 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$가 최소 이동 횟수로 장애물을 모두 넘어갈 수 있는 최적의 방법이다.

당신은 이동 횟수를 최소화하여 모든 장애물을 넘어가는 최적의 방법을 찾고자 한다. 단, 주어진 두 행동만으로 모든 장애물을 넘어가는 것이 불가능한 경우도 있다.

입력

첫 번째 줄에는 $N$이 주어진다.

두 번째 줄에는 $N$개의 정수 $X_1 , X_2 , \cdots , X_N$이 공백을 사이에 두고 차례대로 주어진다.

출력

모든 장애물을 넘어갈 수 없다면, -1을 출력한다.

모든 장애물을 넘어갈 수 있다면, 모든 장애물을 넘기 위해 필요한 최소 이동 횟수를 출력한다.

제한

• 주어지는 모든 수는 정수이다.
• $1 ≤ N ≤ 250\, 000$
• $1 ≤ X_1 < X_2 < \dots < X_N ≤ 250\, 000$

서브태스크

번호	배점	제한
1	7	$N = 1$, $X ≤ 5$
2	12	$N = 1$, $X ≤ 5\, 000$
3	23	$N ≤ 5\, 000$, $1 ≤ i ≤ N$인 모든 $i$에 대하여 $X ≤ 5\, 000$
4	58	추가 제약 조건 없음.

3
2 5 11

7

3
7 20 25

14

4
1 4 5 8

-1