29/07/2025 10:08:01

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2635. Различные числа

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Дана последовательность из $N$ целых чисел. К последовательности можно применять следующую операцию. Выбрать подпоследовательность и увеличить все её элементы на 1. Подпоследовательность – это элементы последовательности с номерами $k_1, k_2, ..., k_m$ , где $m$ – длина подпоследовательности ( $1<=m<=N$ ), $1<=k_1<k_2<...<k_m<=N$ . Необходимо сделать все числа в последовательности различными за наименьшее количество операций. Например, в последовательности 1,2,1,2 можно сделать все числа различными за две операции. Сначала нужно увеличить элементы с номерами 2,3,4, получив последовательность 1,3,2,3, затем увеличить элементы с номерами 2, получив последовательность 1,4,2,3, в которой нет одинаковых элементов.

Первая строка ввода содержит одно целое число $N$ ( $1 <= N <= 10^5$ ). Вторая строка ввода содержит $N$ целых в диапазоне от 1 до $10^6$ .

Вывести одно целое число – наименьшее количество операций, чтобы сделать все числа различными в заданной последовательности.

Пример ввода

4
1 2 1 2

Пример вывода