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

[gamordzhoba]

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

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

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

Пример

Ввод

5
1 4 3 5 2


Вывод

2

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

[virt]

немного не то :

массив 4 3 2 1 можно отсортировать за 2 операции обмена ,а пузырек отсортирует за 6. Аналогично и для любой другой сортировки можно составить подобный тест.

Задачи решается динамически (не путать с динамической памятью) ,только сейчас не знаю как.

ЗЫ
можно и перебором ,но это очень долго.