캠핑장 운반 카트 교대

문제

캠핑장의 보급 통로에는 입구부터 목적지까지 일렬로 놓인 거점들이 있다. 입구는 0번 거점이고 목적지는 N번 거점이며, 이웃한 두 거점 사이의 거리는 모두 같다. 관리자는 입구에 있는 짐 하나를 목적지까지 옮기려 한다. 짐은 각 거점에 준비된 운반 카트에 실어 이동하며, 사용한 카트의 수를 최소화하려 한다. 0번부터 N-1번까지의 각 거점에는 아직 사용하지 않은 카트가 하나씩 있다. i번 거점의 카트에는 이동 한도 A_i가 표시되어 있다. 이 카트를 사용하면 짐을 i번 거점에서 출발시켜 i보다 크고 i+A_i 이하인 번호의 거점 중 하나까지 옮길 수 있다. 목적지를 넘어갈 필요는 없으므로 도착 거점의 번호는 N 이하여야 한다. 이동 거리는 정수 개의 구간으로 정하며, 한도보다 짧게 이동하는 것도 허용한다. 카트 한 대를 사용하는 작업은 출발 거점에서 짐을 싣고 선택한 도착 거점에서 내리는 것까지다. 이동 도중 다른 거점의 카트로 바꿀 수는 없다. 도착한 거점이 목적지가 아니라면 그 거점에 준비된 카트를 새로 사용하여 다음 이동을 시작한다. 이미 사용한 카트를 다시 사용하거나, 다른 거점의 카트를 가져와 사용하는 것은 허용하지 않는다. 이동은 항상 번호가 증가하는 방향으로만 이루어지므로 지나온 거점으로 돌아갈 수도 없다. 이동 한도가 0인 카트는 짐을 다음 거점으로 옮길 수 없다. 따라서 그런 거점에 도착하면 목적지가 아닌 한 더 진행할 수 없다. 어떤 거점의 카트가 멀리 이동할 수 있더라도 그 거점까지 짐을 가져갈 방법이 없으면 이용할 수 없다. 목적지에 도착한 뒤에는 카트를 추가로 사용할 필요가 없다. 가능한 운반 경로가 여러 개이면 경로 자체는 구분하지 않고 사용한 카트 수의 최솟값만 구한다. 모든 거점의 이동 한도가 주어졌을 때 필요한 최소 카트 수를 구하고, 목적지까지 운반할 수 없다면 -1을 출력한다.

입력

첫째 줄에 정수 N이 주어진다. 1 ≤ N ≤ 200,000이다.
둘째 줄에 정수 A_0, A_1, ..., A_(N-1)이 공백으로 구분되어 주어진다. 0 ≤ A_i ≤ 10^9이다. N번 거점은 목적지이므로 해당 거점의 카트 정보는 주어지지 않는다.

출력

짐을 0번 거점에서 N번 거점까지 옮기는 데 필요한 최소 카트 수를 정수 하나로 출력한다. 운반할 수 없으면 -1을 출력한다.

7
3 1 4 1 0 2 1

3

5
2 0 0 4 1

-1

4
4 0 0 0

1

출처: Devin.KR 자체 제작