I. Snakes&Snakes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Vadim has a one-dimensional board for the game Snakes&Snakes, consisting of $$$N$$$ cells numbered from $$$1$$$ to $$$N$$$ from left to right. Initially, a token is placed in cell $$$1$$$. The goal of the game is to reach cell $$$N$$$. Each cell (except for cells $$$1$$$ and $$$N$$$) corresponds to a certain non-negative integer $$$p_i$$$. If $$$p_i = 0$$$, then the $$$i$$$-th cell is empty. Otherwise, there is a teleport in the cell that sends the token to the left. It is guaranteed that cells $$$1$$$ and $$$N$$$ are empty.

In Snakes&Snakes, a move is made according to the following algorithm.

  1. The player rolls a six-sided die. If they roll a number $$$k$$$, they move the token $$$k$$$ cells to the right, ensuring that the token cannot end up to the right of cell $$$N$$$. In other words, if the token was in cell $$$i$$$, it will end up in cell $$$min(i + k, N)$$$;
  2. If the token lands in cell $$$N$$$, the player wins;
  3. If the token lands in the $$$i$$$-th cell, which does not contain a teleport ($$$p_i = 0$$$), the process moves to step $$$4$$$. Otherwise, the token moves left by $$$p_i$$$ cells (to cell number $$$i - p_i$$$), after which step $$$3$$$ is repeated;
  4. If the player rolled a $$$6$$$ on step $$$1$$$, they can repeat all actions of the algorithm starting from step $$$1$$$, without ending the current turn. Otherwise, the current turn of the player ends.

Margo is interested in finding out from Vadim the minimum number of turns required to win this game (even if it is unlikely). Help Vadim answer this question.

Input

The first line contains the number $$$N~(2 \le N \le 2 \cdot 10^5)$$$ — the size of the board.

The second line contains $$$N - 2$$$ numbers $$$p_i~(0 \le p_i \lt i, 1 \lt i \lt N)$$$ — the description of the board.

Output

Output a single number — the minimum number of turns required to win. If it is impossible to reach cell $$$N$$$, output $$$-1$$$.

Examples
Input
10
0 1 1 1 1 1 1 0
Output
-1
Input
10
1 2 1 2 0 1 1 1
Output
1
Input
10
1 1 2 2 0 6 7 8
Output
2