- Описание
- Решения
- Разборы
- Кодерун AI β
630. Мост во дворец
— Как тебе твои новые способности? Неплохо, да? Ну да ладно, я тебе еще всё покажу, но для начала надо поспешить в королевский дворец: принцесса Брейс сегодня устроила бал!
Но... Что это? Мост, ведущий к дворцу принцессы, разрушен! Ещё недавно над рекой висели блоки памяти, но теперь их раскидало по числовой прямой.
Чтобы пройти к дворцу, нужно восстановить мост, переложив блоки так, чтобы они снова непрерывно лежали подряд, один за другим.
Как думаешь, сколько перемещений придётся сделать, чтобы восстановить мост?
Формат ввода
Первый аргумент функции — количество блоков ( ).
Второй аргумент функции представляет собой массив из чисел — координат точек, в которых расположен блок ( ). Гарантируется, что в точке находится не более одного блока.
Формат вывода
Функция должна вернуть минимальное количество перемещений блоков, необходимое для расстановки всех блоков в точках с подряд идущими координатами.
Примечание
В первом примере подходят такие перемещения:
- Переложить блок из точки -3 в точку 1
- Переложить блок из точки 6 в точку 4
После этого все блоки будут расположены в подряд идущих точках с номерами от 0 до 4.
Ограничения
- Ограничение времени
- 2 с
- Ограничение памяти
- 256 МБ
Примеры
Пример 1
5
2 0 -3 3 6
2
Пример 2
1
25
0