Решив все задачи пробного тура, участники ПРОШПа начали скучать в попытках дождаться основной части олимпиады, поэтому после того, как кто-то из школьников предложил поиграть в музыкальные стулья, подавляющее большинство с огнём в глазах поддержало идею скоротать время за этим развлечением.
В начале игры все $$$n$$$ участников берут свои стулья и ставят в круг, а затем нумеруют их по порядку числами от $$$1$$$ до $$$n$$$. Затем для каждого стула с номером $$$i$$$ случайным образом определяется число $$$a_i$$$ — номер стула, на который во время первого перехода должен пересесть ученик, сидящий на $$$i$$$-м стуле. Если несколько школьников хотят переместиться на один и тот же стул, то это делает тот, чей номер предыдущего стула был наименьшим, а остальные выбывают из игры.
Чтобы не загружать себе голову перед олимпиадой и не держать в памяти все переходы, школьник с номером $$$j$$$ запоминает только число $$$a_j$$$, выполняет первый переход по всем описанным выше правилам и запоминает школьника, который сидел на стуле $$$a_j$$$ до него. Далее $$$j$$$-й ученик просто повторяет все действия за $$$a_j$$$-м с отставанием на один переход, в том числе повторяет и выбывание из игры.
После каждого хода те стулья, на которые никто не сел, убирают, чтобы они не мешались, сохраняя при этом нумерацию оставшихся без изменения.
Игра заканчивается, когда последний участник олимпиады покинет игру. Определите, сколько переходов совершит победивший школьник.
В первой строке вводится единственное целое число $$$n$$$ ($$$3 \le n \le 10^6$$$) — количество школьников, участвующих в игре.
Во второй строке вводятся $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le n$$$) — номера стульев, на которые надо пересесть с $$$i$$$-го стула во время перехода.
В единственной строке выведите:
32 3 1
Endless
42 2 4 4
draw
72 3 2 1 4 2 3
4
Объём входных данных в данной задаче велик, поэтому при написании решения настоятельно рекомендуется использовать оптимизации ввода/вывода.
Третий пример можно описать с помощью таблицы, в которой столбцы обозначают номер игрока, строки номер перехода, а значение в клетке таблицы — номер стула, на котором сидит заданный игрок после заданного хода, либо '$$$-$$$', если он к этому ходу уже выбыл.
| Ход | Игрок | $$$\textbf{1}$$$ | $$$\textbf{2}$$$ | $$$\textbf{3}$$$ | $$$\textbf{4}$$$ | $$$\textbf{5}$$$ | $$$\textbf{6}$$$ | $$$\textbf{7}$$$ |
| $$$\textbf{I}$$$ | $$$2$$$ | $$$3$$$ | $$$-$$$ | $$$1$$$ | $$$4$$$ | $$$-$$$ | $$$-$$$ |
| $$$\textbf{II}$$$ | $$$3$$$ | $$$-$$$ | $$$-$$$ | $$$2$$$ | $$$1$$$ | $$$-$$$ | $$$-$$$ |
| $$$\textbf{III}$$$ | $$$-$$$ | $$$-$$$ | $$$-$$$ | $$$3$$$ | $$$2$$$ | $$$-$$$ | $$$-$$$ |
| $$$\textbf{IV}$$$ | $$$-$$$ | $$$-$$$ | $$$-$$$ | $$$-$$$ | $$$3$$$ | $$$-$$$ | $$$-$$$ |
| $$$\textbf{V}$$$ | $$$-$$$ | $$$-$$$ | $$$-$$$ | $$$-$$$ | $$$-$$$ | $$$-$$$ | $$$-$$$ |
Побеждает игрок под номером $$$5$$$, который продержится четыре хода.
Обратите внимание, что игрок номер $$$4$$$ во время четвёртого перехода не пересядет с третьего стула на второй (посмотрев на $$$a_3$$$), а выйдет из игры, повторяя действия игрока номер $$$1$$$.
