60007 장애물 Silver V

문제

위치 0에서 시작하여 수직선 위의 장애물 N개(위치 X_1 < X_2 < … < X_N)를 모두 넘어가야 한다. 다음 두 가지 행동만 가능하다.

• 오른쪽으로 1만큼 걸어가기
• 오른쪽으로 2만큼 점프하기

장애물을 넘어간다는 것은 위치 X_i - 1에서 점프하여 X_i + 1에 도착하는 것을 의미한다. 모든 장애물을 최소 이동 횟수로 넘기거나 불가능함을 판단하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 250,000)이 주어진다.

둘째 줄에 N개의 정수 X_1, X_2, …, X_N이 주어진다. (1 ≤ X_1 < X_2 < … < X_N ≤ 250,000)

출력

모든 장애물을 넘을 수 없으면 -1, 가능하면 최소 이동 횟수를 출력한다.

3
2 5 11

7

3
7 20 25

14

4
1 4 5 8

-1