2194. Snakes&Snakes @ Timus Online Judge

2194. Snakes&Snakes

Time limit: 1.0 second
Memory limit: 256 MB

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.

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);
If the token lands in cell N, the player wins;
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;
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 ≤ N ≤ 2 · 10⁵) — the size of the board.

The second line contains N − 2 numbers p_i (0 ≤ p_i < i, 1 < i < 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.

Samples

input	output
10 0 1 1 1 1 1 1 0	-1
10 1 2 1 2 0 1 1 1	1
10 1 1 2 2 0 6 7 8	2

Problem Author: Vadim Barinov
Problem Source: Ural Regional Contest Qualifier 2023