
PERMUT	Перестановки PERMUTATIONS Теория Напомним, что перестановкой на некотором конечном множестве называется взаимно однозначное отображение этого множества на себя. Менее формально, перестановка — это способ переупорядочить элементы множества. Например, на множестве {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))=P2(n). Более общее определение выглядит так: P(n)=P1(n), Pk(n)=P(Pk-1(n)). Среди всех перестановок особое положение занимает одна — та, которая ничего не переставляет: Совершенно понятно, что для любого k верно соотношение (EN)k=EN. Справедливо и менее тривиальное утверждение (мы не будем здесь его доказывать; решая задачу вы сами попутно получите доказательство): Пусть P(n) некоторая перестановка множества из N элементов. Тогда существует такое натуральное число k, что Pk=EN. Наименьшее натуральное k, такое, что Pk=EN, называется порядком перестановки P. Задача Задача, которую должна решать программа, формулируется теперь очень просто: "Дана перестановка. Найти ее порядок". Технические требования: Входной файл: PERMUT.DAT Выходной файл: PERMUT.SOL Ограничение времени: 5 секунд на тест Входной файл: в первой строке входных данных записано единственное число N, удовлетворяющее двойному неравенству 1<=N<=1000 — количество элементов во множестве, на котором определена перестановка. Далее через пробел, записаны N различных натуральных чисел от 1 до N, задающих перестановку - числа P(1), P(2) …, P(N). Выходной файл: единственное натуральное число - порядок перестановки P. Можно считать, что ответ всегда не превосходит 10⁹. Пример: PERMUT.DAT 5 4 1 5 2 3 PERMUT.SOL 6

PERMUT

Перестановки
PERMUTATIONS

Теория

Напомним, что перестановкой на некотором конечном множестве называется взаимно однозначное отображение этого множества на себя. Менее формально, перестановка — это способ переупорядочить элементы множества. Например, на множестве {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))=P2(n). Более общее определение выглядит так: P(n)=P1(n), Pk(n)=P(Pk-1(n)).

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



Совершенно понятно, что для любого k верно соотношение (EN)k=EN. Справедливо и менее тривиальное утверждение (мы не будем здесь его доказывать; решая задачу вы сами попутно получите доказательство):
Пусть P(n) некоторая перестановка множества из N элементов. Тогда существует такое натуральное число k, что Pk=EN.
Наименьшее натуральное k, такое, что Pk=EN, называется порядком перестановки P.

Задача

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

Технические требования:

Входной файл: PERMUT.DAT
Выходной файл: PERMUT.SOL
Ограничение времени: 5 секунд на тест

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

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

Пример:

PERMUT.DAT
5
4 1 5 2 3

PERMUT.SOL
6