510. Jump Game II

0

Hard

Given an array of non-negative integers arr, a monkey starts at the first index of the array. Each element in the array arr[i] represents the maximum length of a forward jump from index i. The monkey wants to reach the last index in the minimum number of jumps. Help the monkey find the minimum number of jumps required to reach the last index. It is guaranteed that the monkey can always reach the last index.

Input Format

The first line of input should contain an integer N, the size of the array. The second line should contain N integers, representing the elements of the array.

Output Format

Print the minimum number of jumps the monkey needs to reach the last index.

Example

Input

5
2 3 1 1 4

Output

2

Constraints

1<=N<=10^4

0<=arr[i]<=1000

0<=arr[i]<=1000

Loading...

View Submissions

Console