print958. Сортировка списка

printСортировка списка

Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Представьте себе линейный список, содержащий в некотором порядке все натуральные числа от 1 до `N`. Разрешается перемещать любой элемент в любое место списка. Перемещение одного элемента занимает одну единицу времени. Ваша задача – определить минимальное время, за которое список может быть упорядочен по возрастанию.
Ввод
В первой строке входного файла записано целое число `N` (`1\ ≤\ N\ ≤\ 10^5`). В остальных строках записаны числа, содержащиеся в списке.
Вывод
Запишите в выходной файл слово наименьшее время, за которое можно упорядочить список.

Пример ввода 1

5
1 2 3 4 5

Пример вывода 1

0

Пример ввода 2

9
1 3 7 4 6 8 5 9 2

Пример вывода 2

3
Источник: Весенний турнир имени Мартовского Зайца, 2007
loading