e-olymp
Yarışlar

2018 USACO January

Не на месте

Чувствуя себя амбициозным, фермер Джон планирует попытаться сделать то, что, кажется, никогда не получится: он хочет сфотографировать все свое стадо коров.

Чтобы фотография выглядела красиво, он хочет, чтобы коровы выстроились в один ряд от самых коротких до самых высоких. К сожалению, сразу после того, как коровы выстроились таким образом, корова Бесси, всегда нарушающая спокойствие, выходит из строя и снова вставляется в какое-то другое место в очереди!

Фермер Джон хотел бы поменять местами коров, чтобы все стадо снова было правильно выстроено в очередь. Помогите ему определить минимальное количество обменов между парами коров для достижения этой цели.

Входные данные

Первая строка содержит число n (2n100). Следующие n строк описывают рост коров, выстроившихся в очередь после того, как Бесси сделала переход. Высота каждой коровы - целое число в диапазоне 1 ... 106. Коровы могут иметь одинаковый рост.

Выходные данные

Выведите минимальное количество раз, которое фермеру Джону необходимо поменять пары коров, чтобы добиться правильного порядка. Обмены не обязательно должны включать в сеья соседних коров.

Пример

В этом примере Бесси явно корова ростом 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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
6
2
4
7
7
9
3
Çıxış verilənləri #1
3
Mənbə 2018 USACO Январь, Бронза