Question
Luna's Minimum Jumps
Luna, an adventurous explorer, has devised a jumping challenge for herself. She starts at the beginning of a path, represented by an array of non-negative integers. Each number in the array indicates the maximum distance Luna can jump from that spot. Her goal is to reach the last position on the path using the fewest jumps possible. Your mission is to help Luna determine the minimum number of jumps she needs to reach the end of her journey.
Input
The first line of input contains a single integer N, denoting the number of elements in the array.
The next line of the input contains n space-separated elements of the array, A1, A2, ... , An
Constraints
1 ≤ N ≤ 200000
1 ≤ A[i] ≤ 100000
There is always a way to reach the last index.
The next line of the input contains n space-separated elements of the array, A1, A2, ... , An
Constraints
1 ≤ N ≤ 200000
1 ≤ A[i] ≤ 100000
There is always a way to reach the last index.
Output
Output a single integer, the minimum number of required jumps.
Example
Sample Input
5
2 3 1 1 4
Sample Output
2
Explanation
The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 1 to 2, jump 2 from 2 to last index 5.
5
2 3 1 1 4
Sample Output
2
Explanation
The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 1 to 2, jump 2 from 2 to last index 5.