| Codeforces Round 523 (Div. 2) |
|---|
| Закончено |
Вы пришли на выставку и один экспонат привлёк ваше внимание. Он состоит из $$$n$$$ колонн, где $$$i$$$-я колонна состоит из $$$a_i$$$ блоков стоящих на полу.
Высота экспоната равна $$$m$$$, а значит количество блоков в каждой колонне не превосходит $$$m$$$.
На потолке есть камера, которая снимает вид экспонат сверху, а также ещё одна камера расположена сбоку и снимает боковой вид этого экспоната.
Выясните какое наибольшее количество блоков можно удалить так, чтобы вид ни из первой камеры, ни из второй не поменялся.
Обратите внимание, что изначально все блоки «прижаты» к полу, однако не требуется, чтобы это было верно после удаления удаляемых блоков. На экспонат не действует гравитация, а значит ни один блок не упадёт вниз, даже если убрать блок под ним. Перемещать блоки вручную также не разрешается.
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 100\,000$$$, $$$1 \le m \le 10^9$$$) — количество колонн и высота всего экспоната.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — количества блоков в каждой колонне слева направо.
Выведите одно целое число — наибольшее количество блоков, которое можно удалить.
5 6
3 3 3 3 3
10
3 5
1 2 4
3
5 5
2 3 1 4 4
9
1 1000
548
0
3 3
3 1 1
1
Следующие картинки иллюстрируют первый пример и его возможное решение.
Синие клетки иллюстрируют удалённые блоки. Всего есть $$$10$$$ синих клеток, а значит ответ $$$10$$$.
