ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1024. Перестановки

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

Вступление

Напомним, что перестановкой на некотором конечном множестве называется взаимно однозначное отображение этого множества на себя. Менее формально, перестановка — это способ переупорядочить элементы множества. Например, на множестве {1, 2, 3, 4, 5} можно задать перестановку
Problem illustration
Такая запись определяет перестановку 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)) тоже перестановка. В нашем примере (проверьте!)
Problem illustration
Естественно тогда обозначить эту перестановку так: P(P(n))=P2(n). Более общее определение выглядит так: P(n)=P1(n), Pk(n)=P(Pk-1(n)).
Среди всех перестановок особое положение занимает одна — та, которая ничего не переставляет:
Problem illustration
Совершенно понятно, что для любого k верно соотношение (EN)k=EN. Справедливо и менее тривиальное утверждение (мы не будем здесь его доказывать; решая задачу вы сами попутно получите доказательство):
Пусть P(n) — некоторая перестановка множества из N элементов. Тогда существует такое целое положительное число k, что Pk=EN.
Наименьшее целое положительное k, такое, что Pk = EN, называется порядком перестановки P.

Задача

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

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

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

Результат

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

Пример

исходные данныерезультат
5
4 1 5 2 3
6
Автор задачи: Никита Шамгунов
Источник задачи: Второе командное соревнование школьников Свердловской области по программированию, 7 октября 2000