A pond has n lily pads in a line, numbered 0 to n-1. Standing on pad i, a frog can hop forward to any pad j with i < j <= i + a_i, where a_i is the maximum hop distance printed on pad i. Starting on pad 0, find the minimum number of hops needed to reach pad n-1. If pad n-1 cannot be reached, print -1.
Input format
Line 1: an integer n.
Line 2: n space-separated integers a_0 a_1 ... a_{n-1}.
Output format
A single integer: the minimum number of hops needed to reach pad n-1 from pad 0, or -1 if it cannot be reached.
Constraints
- 1 <= n <= 40
- 0 <= a_i <= 40