Напомним, что перестановкой на некотором конечном множестве называется взаимно однозначное отображение этого множества на себя. Менее формально, перестановка — это способ переупорядочить элементы множества. Например, на множестве {1, 2, 3, 4, 5} можно задать перестановку

Такая запись определяет перестановку P следующим образом: P(1)=4, P(2)=1, P(3)=5 и т.д.

А чему равно значение выражения P(P(1))? Совершенно понятно — P(P(1))=P(4)=2. А, например, P(P(3))=P(5)=3. Легко понять, что если P(n) — перестановка, то и P(P(n)) тоже перестановка. В нашем примере (проверьте!)

Естественно тогда обозначить эту перестановку так: P(P(n))=P²(n). Более общее определение выглядит так: P(n)=P¹(n), P^k(n)=P(P^k-1(n)).

Среди всех перестановок особое положение занимает одна — та, которая ничего не переставляет:

Совершенно понятно, что для любого k верно соотношение (E_N)^k=E_N. Справедливо и менее тривиальное утверждение (мы не будем здесь его доказывать; решая задачу вы сами попутно получите доказательство):

Наименьшее целое положительное k, такое, что P^k = E_N, называется порядком перестановки P.

Задача, которую должна решать программа, формулируется теперь очень просто: «дана перестановка, найти ее порядок».

В первой строке записано единственное целое число N, удовлетворяющее двойному неравенству 1 ≤ N ≤ 1000 — количество элементов во множестве, на котором определена перестановка. Во второй строке через пробел записаны N различных целых чисел от 1 до N, задающих перестановку — числа P(1), P(2) … P(N).

Выведите порядок перестановки P. Можно считать, что ответ всегда не превосходит 10⁹.