Не на місці#10419
Фермер Джон налаштований амбітно. Він хоче спробувати зробити те, що ніколи до ладу не вдається: сфотографувати все своє стадо корів.
Щоб фотографія вийшла гарною, він просить корів вишикуватися в один ряд за зростом, від найнижчої до найвищої. На жаль, одразу після того як йому вдається вишикувати корів, корова Бессі — вічна порушниця порядку — виходить зі строю і стає назад на інше місце в ряду!
Тепер Фермер Джон хоче міняти місцями пари корів так, щоб усе стадо знову було вишикуване правильно, від найнижчої до найвищої. Допоможіть йому визначити найменшу кількість обмінів, необхідну для відновлення правильного порядку. Корови, яких міняють місцями, не обов'язково мають стояти поруч.
Перший рядок містить одне ціле число n~(2 \le n \le 100) — кількість корів. Кожен з наступних рядків містить одне ціле число: зріст корови в поточному ряду, після того як Бессі змінила своє місце. Кожен зріст є цілим числом від до 10^6. Кілька корів можуть мати однаковий зріст.
Виведіть одне ціле число: найменшу кількість обмінів, яку має виконати Фермер Джон, щоб повернути ряд до відсортованого порядку.
У наступному прикладі Бессі, очевидно, є коровою зросту . Фермер Джон повертає корів до відсортованого порядку за три обміни, як показано нижче:
2~4~7~7~9~3 — початковий ряд
2~4~7~7~3~9 — міняємо місцями двох останніх корів
2~4~3~7~7~9 — міняємо місцями першу і
2~3~4~7~7~9 — міняємо місцями і
Приклад 1