НачалоПодразделы
Другие разделы
| 954. Олимпиада |
| 955. Оффшорное программирование |
| 956. Многоугольник |
| 957. Стена |
| 959. Разбиение матрицы |
| 960. Обобщённые матрёшки |
| 961. Узелки |
| 962. Цепные дроби |
| 963. Унарная система счисления |
| 964. Башня |
Дата и время
22/12/2024 15:38:03
958. Сортировка списка
Сортировка списка
Задачи на идеюДерево отрезков, декартово дерево, √-декомпозиция
Олимпиадные задачи на русском языке
| 03/07/2008 | Лето 2008 дорешивание ( 4E) |
| 09/07/2008 | Лето 2008 - 4 (E) |
Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
