문제
바닥에 n개의 스프링들이 같은 간격으로 놓여 있다.
첫 번째 스프링에서 출발하여, 당신은 스프링 위에서 공을 튀기면서 마지막(n번째) 스프링까지 도달하려 한다.
매번 공을 튀길 때, 공을 움직일 수 있는 범위는 스프링의 탄성력에 따라서 정해진다.
이 탄성력은 스프링마다 다를 수도 있다. i번째 스프링의 탄성력을 Pi라 할 때, i번째 스프링에서 공을 튀기면 i-Pi번째 스프링부터 i+Pi번째 스프링으로 이동할 수 있다.
예를 들어 P5 = 3이고, 공을 5번 스프링에서 튀기면, 공은 2,3,4,5,6,7,8번 스프링 중 하나로 이동할 수 있다.
스프링에서 공을 튀길 때마다 스프링의 수명이 조금씩 닳기 때문에, 당신은 스프링을 최소 회수로 사용하여 마지막 스프링에 도달하려 한다.
각 스프링의 탄성력이 주어졌을 때, 첫 번째 스프링에서 시작하여 최소 몇 번 스프링에 공을 튀겨야 마지막 스프링에서 도달할 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 스프링의 개수를 나타내는 자연수 n(1≤n≤1 000,000)이 주어진다.
두 번째 줄부터는 차례로 P1, P2, ..., Pn이 주어진다. 이 값들은 한 개 이상의 공백문자로 분리되어 있다. 각각의 1≤i≤n에 대해서 Pi는 1≤Pi≤n을 만족한다.
출력
스프링의 최소 사용 회수를 출력한다.
예제
10
3 2 1 2 1 2 1 2 3 1
4
로그인해야 코드를 작성할 수 있어요.