Minimum Jumps to Reach the Last Stall

Problem Statement

At the village fair, all the children have been asked to participate in a game. A certain number of stalls are arranged in a straight line. All the children start at the first stall, and the child who reaches the last stall earliest wins. At each stall, a token number is displayed using which a child can skip some stalls in between. If a token of "p" is displayed at a stall, the child can then go to any of the next "p" stalls. At every stall the child visits, there is a wait time of five minutes, so the fewer stalls one visits, the more likely they are to win.

Jaya, who was at the fair, was also told to participate. Being very competitive, she wants to win desperately. Can you write a program to help her?

The token numbers of the N stalls are given as an array A = [A1, A2, ..., AN]. Write a program to determine the minimum number of moves Jaya needs to reach the last stall from the first.

Read the input from STDIN and print the output to STDOUT. Do not print arbitrary strings anywhere in the program, as these contribute to the standard output and test cases will fail.

Constraints

• 2 <= N <= 1000
• 1 <= Ai <= 100 for all i ranging from 1 to N.

Input Format

A single line of input consists of the array A, which has N number of space-separated positive integers denoting the tokens (so, Jaya has to move only in the forward direction).

Output Format

A single line of output should print the minimum number of moves that Jaya needs to make, to reach the last stall from the first.

Sample Input 1

4 4 2 1 4 4 1 2

Sample Output 1

2

Explanation 1

The token array, A = [4, 4, 2, 1, 4, 4, 1, 2].

Jaya is at the 1st stall and its token number is 4. So, Jaya can visit any of the next 4 stalls i.e. stall numbers 2, 3, 4, or 5, which have token numbers 4, 2, 1 and 4, respectively.

As her first move, Jaya chooses stall 5 whose token number is again 4. She can therefore next visit stalls 6, 7, 8 or 9. Since there are only 8 stalls, Jaya in her second move can immediately visit the last stall.

Since she needs 2 moves to reach the last stall from the first, 2 is printed as the output.

Sample Input 2

2 4 1 3 2 1 1

Sample Output 2

3

Explanation 2

The token array, A = [2, 4, 1, 3, 2, 1, 1].

Jaya is at the 1st stall, and the token number is 2. So, as her first move, Jaya can visit either stall 2 or stall 3. She chooses stall 2 whose token is 4. As her second move, she moves to stall 6 which has token 1. As her third move she visits the last stall, hence output is 3.

Alternately, Jaya in her second move can visit stall 4, with token 3. In her third move, she can visit the last stall. Here also output is 3.

So there are multiple ways, but minimum 3 moves are needed. Therefore 3 is printed as the output.