Snakes&Snakes
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Вадима есть одномерная доска для игры в Snakes&Snakes, состоящая из $$$N$$$ клеток, которые пронумерованы от $$$1$$$ до $$$N$$$ слева направо. Изначально в клетке $$$1$$$ стоит фишка. Цель игры — попасть в клетку $$$N$$$. Каждой клетке (кроме клеток $$$1$$$ и $$$N$$$) соответствует некоторое целое неотрицательное число $$$p_i$$$. Если $$$p_i = 0$$$, то $$$i$$$-я клетка пустая. В противном случае в клетке стоит телепорт, отправляющий фишку влево. Гарантируется, что клетки $$$1$$$ и $$$N$$$ пустые.

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

  1. Игрок бросает шестигранный кубик. Если ему выпало число $$$k$$$, то он двигает фишку на $$$k$$$ клеток вправо, при этом фишка не может оказаться правее клетки $$$N$$$. Другими словами, если фишка стояла в клетке $$$i$$$, то она оказывается в клетке $$$min(i + k, N)$$$;
  2. Если фишка оказалась в клетке $$$N$$$, то игрок побеждает;
  3. Если фишка оказалась в $$$i$$$-й клетке, которая не содержит телепорт ($$$p_i = 0$$$), то происходит переход к шагу $$$4$$$. В противном случае фишка перемещается влево на $$$p_i$$$ клеток (в клетку с номером $$$i - p_i$$$), после чего повторяется шаг $$$3$$$;
  4. Если игрок на шаге $$$1$$$ выбросил на кубике $$$6$$$, то он может повторить все действия алгоритма, начиная с шага $$$1$$$, не прекращая текущий ход. В противном случае текущий ход игрока завершается.

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

Входные данные

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

Во второй строке даны $$$N - 2$$$ числа $$$p_i~(0 \le p_i < i, 1 < i < N)$$$ — описание доски.

Выходные данные

Выведите одно число — минимальное число ходов, необходимое для победы. Если добраться до клетки $$$N$$$ нельзя, то выведите $$$-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