You stand on index 0 of a zero-indexed array a of length n. From index i you may jump forward to any index i + k where 1 <= k <= a[i] (a value of 0 means you cannot move from that index). You never jump past the last index, and you never move backward.
Compute the minimum number of jumps needed to reach the last index (index n - 1). If the last index cannot be reached, print -1. When n = 1 you are already at the end, so the answer is 0.
Input format
Line 1: an integer n, the array length.
Line 2: n space-separated non-negative integers, the array a.
Output format
A single integer: the minimum number of jumps to reach the last index, or -1 if it is unreachable.
Constraints
- 1 <= n <= 100000
- 0 <= a[i] <= 100000