Не на месте
Чувствуя себя амбициозным, фермер Джон планирует попытаться сделать то, что, кажется, никогда не получится: он хочет сфотографировать все свое стадо коров.
Чтобы фотография выглядела красиво, он хочет, чтобы коровы выстроились в один ряд от самых коротких до самых высоких. К сожалению, сразу после того, как коровы выстроились таким образом, корова Бесси, всегда нарушающая спокойствие, выходит из строя и снова вставляется в какое-то другое место в очереди!
Фермер Джон хотел бы поменять местами коров, чтобы все стадо снова было правильно выстроено в очередь. Помогите ему определить минимальное количество обменов между парами коров для достижения этой цели.
Входные данные
Первая строка содержит число 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