Fewest Jumps to the End

Difficulty: 1600 3000 ms 128 MB

greedy

Same jumping rule (from i you may advance up to a_i), but now print the minimum number of jumps to reach position N, or −1 if it is unreachable.

Input: the first line has N; the second line has N non-negative integers.

Output: the minimum number of jumps, or −1.

Constraints:

• 1 ≤ N ≤ 10⁵
• 0 ≤ a_i ≤ 10⁵

Sample Tests

5
2 3 1 1 4

2

5
3 2 1 0 4

-1

Read the Editorial