There are n stepping stones in a row, numbered 0 to n-1. Stone i has a maximum leap distance a_i, meaning that from stone i you may jump directly to any stone i+1, i+2, ..., i+a_i (never past the last stone). Starting on stone 0, find the minimum number of leaps needed to reach stone n-1. If it cannot be reached, print -1.
Input format
Line 1: an integer n.
Line 2: n space-separated non-negative integers a_0 ... a_{n-1}.
Output format
A single integer: the minimum number of leaps to reach stone n-1 from stone 0, or -1 if it is impossible. (If n <= 1, you are already there, so the answer is 0.)
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ a_i ≤ n