2194. Snakes&Snakes @ Timus Online Judge

2194. Snakes&Snakes

Ограничение времени: 1.0 секунды
Ограничение памяти: 256 МБ

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

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

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

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

Исходные данные

В первой строке дано число N (2 ≤ N ≤ 2 · 10⁵) — размер доски.

Во второй строке даны N − 2 числа p_i (0 ≤ 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

Автор задачи: Вадим Баринов
Источник задачи: Квалификационный тур Уральского регионального чемпионата ICPC 2023