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