Перестановкой называется последовательность из N чисел от 1 до N, в которой каждое из чисел встречается ровно один раз. Перестановку можно рассмотреть как правило перестановки элементов. Например, рассмотрим такую перестановку: 5 2 6 7 3 1 4. Итак, запишем друг под другом исходную перестановку и переставленную:
1 2 3 4 5 6 7 5 2 6 7 3 1 4
Это обозначает, что элемент, стоявший на первом месте, оказывается на шестом, стоявший на втором - остается на месте, стоявший на третьем - оказывается на пятом и т.д. Давайте в полуенной последовательности переставим числа по тому же правилу, т.е. стоящее на первом месте - на шестое и так далее. Получим последовательность:
3 2 1 4 6 5 7Далее получим последовательности:
6 2 5 7 1 3 4 1 2 3 4 5 6 7
Видно, что рано или поздно каждое число возвращается на свое место. Если проследить путь каждого числа, то оно последовательно оказывается на разных местах, например, число 1 оказывается на местах 1, 6, 3, 5, 1... Нетрудно заметить, что на самом деле числа 1, 6, 3, 5 каждый раз сдвигаются по циклу и оказываются на местах друг друга. Говорят, что они образуют цикл в нашей перестановке. Всю перестановку можно разбить на непересекающиеся циклы - в нашем примере их три: цикл из чисел 1, 6, 3, 5, цикл из чисел 4, 7 и цикл из одного числа, которое всегда стоит на своем месте - числа 2.
Напишите программу, которая по заданной перестановке вычислит количество циклов в ней.
Входные данные. Вводится натутальное число N (от 1 до 100) и далее перестановка из N элементов.
Выходные данные. Выведите одно число - количество циклов в этой перестановке.
| Пример ввода | Пример вывода |
7 5 2 6 7 3 1 4 |
3 |