Snakes&Snakes

문제

У Вадима есть одномерная доска для игры в Snakes&Snakes, состоящая из $NN$ клеток, которые пронумерованы от $11$ до $NN$ слева направо. Изначально в клетке $11$ стоит фишка. Цель игры --- попасть в клетку $NN$. Каждой клетке (кроме клеток $11$ и $NN$) соответствует некоторое целое неотрицательное число $p_{i}p\_i$. Если $p_i=0p\_i\; =\; 0$, то $ii$-я клетка пустая. В противном случае в клетке стоит телепорт, отправляющий фишку влево. Гарантируется, что клетки $11$ и $NN$ пустые.

В Snakes&Snakes ход совершается по следующему алгоритму.

1. Игрок бросает шестигранный кубик. Если ему выпало число $kk$, то он двигает фишку на $kk$ клеток вправо, при этом фишка не может оказаться правее клетки $NN$. Другими словами, если фишка стояла в клетке $ii$, то она оказывается в клетке $min(i+k,N)min(i\; +\; k,\; N)$;
2. Если фишка оказалась в клетке $NN$, то игрок побеждает;
3. Если фишка оказалась в $ii$-й клетке, которая не содержит телепорт ($p_i=0p\_i\; =\; 0$), то происходит переход к шагу $44$. В противном случае фишка перемещается влево на $p_{i}p\_i$ клеток (в клетку с номером $i-p_{i}i\; -\; p\_i$), после чего повторяется шаг $33$;
4. Если игрок на шаге $11$ выбросил на кубике $66$, то он может повторить все действия алгоритма, начиная с шага $11$, не прекращая текущий ход. В противном случае текущий ход игрока завершается.

Марго интересуется у Вадима, за какое минимальное количество ходов можно победить в этой игре (даже если это маловероятно). Помогите Вадиму ответить на данный вопрос.

입력

В первой строке дано число $N(2\le N\le 2\cdot {10}^5)N\; (2\; \backslash le\; N\; \backslash le\; 2\; \backslash cdot\; 10^5)$ --- размер доски.

Во второй строке даны $N-2N\; -\; 2$ числа --- описание доски.

출력

Выведите одно число --- минимальное число ходов, необходимое для победы. Если добраться до клетки $NN$ нельзя, то выведите $-1-1$.

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