630. Мост во дворец

Не решаласьСредняя

— Как тебе твои новые способности? Неплохо, да? Ну да ладно, я тебе еще всё покажу, но для начала надо поспешить в королевский дворец: принцесса Брейс сегодня устроила бал!

Но... Что это? Мост, ведущий к дворцу принцессы, разрушен! Ещё недавно над рекой висели блоки памяти, но теперь их раскидало по числовой прямой.

Чтобы пройти к дворцу, нужно восстановить мост, переложив блоки так, чтобы они снова непрерывно лежали подряд, один за другим.

Как думаешь, сколько перемещений придётся сделать, чтобы восстановить мост?

Формат ввода

Первый аргумент функции N N — количество блоков ( 1 ≤ N ≤ 1 0 5 1 \le N \le 10^5 ).

Второй аргумент функции представляет собой массив из N N чисел a i a_i — координат точек, в которых расположен блок ( − 1 0 9 ≤ a i ≤ 1 0 9 -10^9 \le a_i \le 10^9 ). Гарантируется, что в точке находится не более одного блока.

Формат вывода

Функция должна вернуть минимальное количество перемещений блоков, необходимое для расстановки всех N N блоков в N N точках с подряд идущими координатами.

Примечание

В первом примере подходят такие перемещения:

  • Переложить блок из точки -3 в точку 1
  • Переложить блок из точки 6 в точку 4

После этого все блоки будут расположены в подряд идущих точках с номерами от 0 до 4.

Ограничения

Ограничение времени
2 с
Ограничение памяти
256 МБ

Примеры

Пример 1

Ввод
5
2 0 -3 3 6
Вывод
2

Пример 2

Ввод
1
25
Вывод
0

Теги

3.7.2
Нужно войти, чтобы отправить решение.Войти