674. The Unusual Staircase

0

Easy

Given a representation of a staircase with 'N' steps (0 to n-1), each step is labeled with a number x[i] (for the ith step). At each step, there are two choices: either proceed to the next step (i+1) or jump x[i] steps from the current step (to the i+x[i]th step). If the number written on the step is less than 0, it is possible to come down that many steps or climb one step up. Sanchit starts at the 0th step and needs to find the minimum number of jumps required to reach the top of the staircase (the nth step). If it is not possible to reach the top, -1 should be printed. Otherwise, the minimum number of jumps needed should be printed. Note that any jump resulting in a step greater than n is considered an invalid move.

Input Format

The first line contains N, the number of steps. The second line contains the array elements representing the numbers on each step.

Output Format

Print the minimum number of steps required to reach the top of the staircase.

Example

Input

6
-1 2 1 3 -3 3

Output

3

Constraints

1<=T<=1000

1<=n<=20

-17<=x[i]<=17 and x[i] != 0

1<=n<=20

-17<=x[i]<=17 and x[i] != 0

Loading...

View Submissions

Console