Jump Jump

Interview

Time limit1sMemory limit256 MB

Summary

Starting from the first cell, find the fewest rightward jumps bounded by each cell value to reach the last cell, or -1 when unreachable.

Level: Medium4 of 10
Topics: Dynamic programming, Greedy
Solved: No attempts yet

Problem

Jaehwan is trapped in a maze of size 1×N. The maze is a single row of N cells of size 1×1, and each cell holds one integer. Let $A_i$ be the number written on cell i. From cell i, Jaehwan can jump in one move to a cell at most $A_i$ positions to the right. For example, if cell 3 holds the number 3, he can jump to cell 4, cell 5, or cell 6.

Jaehwan stands on the leftmost cell and wants to reach the rightmost cell. Write a program that finds the smallest number of jumps he needs. If he cannot reach the rightmost cell, print -1.

Input

The first line contains N ( $1 \le N \le 1000$ ).

The second line contains $A_1, A_2, \dots, A_N$ separated by spaces ( $0 \le A_i \le 100$ ).

Output

Print the minimum number of jumps needed to reach the rightmost cell on one line. If the rightmost cell cannot be reached, print -1.

Examples4

Example 1
Input
```
10
1 2 0 1 3 2 1 5 4 2
```
Expected output
```
5
```
Example 2
Input
```
1
0
```
Expected output
```
0
```
Example 3
Input
```
2
0 5
```
Expected output
```
-1
```
Example 4
Input
```
2
1 0
```
Expected output
```
1
```