Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
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
