НачалоПодразделы
Дата и время
21/11/2024 23:52:27
Лето 4
A. Олимпиада B. Оффшорное программирование C. Многоугольник D. Стена E. Сортировка списка F. Разбиение матрицы G. Обобщённые матрёшки H. Узелки I. Цепные дроби J. Унарная система счисления K. Башня
E. Сортировка списка
Задачи на идеюДерево отрезков, декартово дерево, √-декомпозиция
Олимпиадные задачи на русском языке
| 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
