Перестановки Опции

[gamordzhoba]

Дана перестановка. Наименьшее число обменов, чтобы ее отсортировать.

Входные данные
Число N (1 <= N <= 10000), затем перестановка.

Выходные данные
Выведите ответ.

Пример

Ввод

5
1 4 3 5 2


Вывод

2

Что то не получается.

[volvo]

Нашел вот такой алгоритм (на форуме AlgoList-а) :

Объясню алгоритм на примере: нам дано 5 чисел (перестановка)
4 3 2 5 1
Чтобы 1 оказалось на своем месте, нужно куда-то деть 4. Лучше деть 4 на ее место. Но тогда нужно деть куда-то 5. А 5 нужно деть туда, где 1!

Поэтому требуется найти все такие цепочки чисел a1,a2,..ak, где a1 стоит на месте a2, a2 стоит на мете a3 и т.д., ak стоит на месте a1. В этом примере будут такие цепочки:
4 1 5
3 2
А наименьшее количество таких перемещений, за которое можно это дело отсортировать, есть сумма длин всех таких цепочек. То есть эта сумма равна количеству элементов, которые не совпадают с номером своего места.
Поэтому когда у нас не перестановка, а просто набор чисел, нужно сначала подсчитать порядковую статистику каждого элемента (O(n*log(n)), если использовать быструю сортировку), а потом подсчитать количество элементов, которые стоят "не на своем месте". Это количество и есть минимальное возможное число перемещений.