Для обеспечения сохранности пользовательских данных Аркадий постоянно изобретает и тестирует новые схемы организации резервного копирования. В этот раз он пронумеровал все имеющиеся у него компьютеры с данными от 1 до n и для каждого компьютера с номером от 1 до n - 1 назначил резервный компьютер p_i. При этом он строго соблюдал правило, что номер компьютера для резервного копирования всегда больше номера самого компьютера, то есть p_i > i. По этой причине, у компьютера с номером n компьютера для резервного копирования нет.

В ходе текущего эксперимента Аркадий выбрал некоторую конфигурацию значений p_i и будет последовательно отключать компьютеры по одному каждую секунду. Эксперимент заканчивается, когда Аркадий отключает компьютер с номером n. Изначально, на каждом компьютере находится некоторый блок данных размера 1. При отключении компьютера с номером x, изначально расположенный на нём блок данных размера 1 передаётся на компьютер с номером p_x, при этом, если на компьютере номер x находилось другие блоки данных (полученные от других компьютеров при их отключении), то они исчезают. Если же компьютер p_x уже отключен, то и блок данных с компьютера x никуда не передаётся и тоже исчезает.

Аркадий хочет, чтобы эксперимент продолжался как можно дольше, но он вынужден соблюдать ещё одно дополнительное ограничение: если на каком-либо компьютере собирается k блоков данных, то в целях сохранности железа этот компьютер необходимо тут же выключить в течение следующей секунды. Обратите внимание, что последняя секунда (во время которой выключается компьютер n) не учитывается.