У одного моего знакомого жена просто ужасная: она находит деньги, где бы он их не прятал, и забирает все. Поэтому он всегда пытается найти новое место для тайника. Их отношения дошли до того, что мой знакомый решил распределять деньги по тайниках - мол, если жена и найдет, то далеко не все. Что ж, разумно.

Но перед ним встал вопрос: куда положить основную часть денег, которую жена не должна найти? Она равновероятно заглянет в любой из тайников. Единственный выход, который нашел бедняга - каждый день переносить деньги с одного тайника в другой. Это надо делать быстро (чтобы жена не увидела), поэтому пересчитывать деньги времени нет - и поэтому мой приятель записал на листке схему, по которой в дальнейшем перекладывал деньги между тайниками. Чтобы контролировать свои капиталы, приятель записал дату, когда схема была составлена, и пронумеровал на ней тайники, обозначив цифрой "1" тайник, где в тот момент находились основные запасы «на черный день».

Но неудачник вскоре оставил схему без присмотра ... и ее сразу же нашла жена! Она увидела отметку и решила найти скрытую наибольшую «заначку». Своей неординарной логикой она поняла, что рано или поздно эта заначка снова вернется в первый тайник. Поэтому она решила подсчитать, за сколько дней с момента составления схемы все скрытые деньги вернутся на те места, где они находились в день составления схемы.

Жена моего знакомого, как это ни печально, обратилась ко мне за помощью. А я, в свою очередь, обращаюсь к Вам.

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

Первая строка содержит количество тайников n (0 < n < 15000), а вторая – последовательность из n целых чисел, являющихся схемой перекладывания, где i-ое число обозначает номер тайника, куда каждый день перекладывается содержимое i-го тайника.

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

Вывести одно число - количество дней, за которое содержимое тайников вернется в исходное состояние.