A climber crosses a quarry along n ledges numbered 0 to n-1, starting on ledge 0. From ledge i the climber can leap forward to any ledge j with i < j <= i + a[i], where a[i] is the maximum forward reach from ledge i (a reach of 0 means no leap is possible from that ledge). The climber only moves forward.
Report the minimum number of leaps needed to reach the last ledge (ledge n-1). If the last ledge cannot be reached, report -1. If the climber already starts on the last ledge, the answer is 0.
Input format
Line 1: the integer n.
Line 2: n space-separated non-negative integers a[0] a[1] ... a[n-1].
Output format
A single integer: the fewest leaps to reach the last ledge, or -1 if impossible.
Constraints
- 1 <= n <= 40
- 0 <= a[i] <= 1000000000