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.
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.
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 a single number — the minimum number of turns required to win. If it is impossible to reach cell $$$N$$$, output $$$-1$$$.
100 1 1 1 1 1 1 0
-1
101 2 1 2 0 1 1 1
1
101 1 2 2 0 6 7 8
2