A. Монстры (простая версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. В этой версии задачи ответ нужно вычислить один раз. В этой версии задачи взломы запрещены.

В компьютерной игре вы сражаетесь против $$$n$$$ монстров. Монстр с номером $$$i$$$ имеет $$$a_i$$$ единиц здоровья, где $$$a_i$$$ — целое число. Монстр жив, пока имеет хотя бы $$$1$$$ единицу здоровья.

Вы можете использовать заклинания двух типов:

  1. Нанести $$$1$$$ единицу урона любому живому монстру на ваш выбор.
  2. Нанести $$$1$$$ единицу урона всем живым монстрам. Если хотя бы один монстр умирает (оказывается с $$$0$$$ единицами здоровья) в результате этого действия — повторить его (и продолжать повторять, пока хотя бы один монстр умирает после каждого применения).

При нанесении $$$1$$$ единицы урона здоровье монстра уменьшается на $$$1$$$.

Заклинания типа 1 могут быть использованы сколько угодно раз, а заклинание типа 2 — не более одного раза за игру.

Какое наименьшее число раз вам нужно применить заклинания типа 1, чтобы убить всех монстров?

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — число монстров.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — число единиц здоровья у монстров.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — наименьшее число раз, которое нужно применить заклинания типа 1, чтобы убить всех монстров.

Пример
Входные данные
2
3
3 1 2
6
4 1 5 4 1 1
Выходные данные
0
4
Примечание

В первом наборе входных данных начальные значения здоровья у монстров равны $$$[3, 1, 2]$$$. Достаточно применить заклинание типа 2:

  • Здоровья монстров становятся равны $$$[2, 0, 1]$$$. Так как монстр номер $$$2$$$ умер, заклинание повторяется.
  • Здоровья монстров становятся равны $$$[1, 0, 0]$$$. Так как монстр номер $$$3$$$ умер, заклинание повторяется.
  • Здоровья монстров становятся равны $$$[0, 0, 0]$$$. Так как монстр номер $$$1$$$ умер, заклинание повторяется.
  • Здоровья монстров становятся равны $$$[0, 0, 0]$$$.

Так как можно обойтись вообще без заклинаний типа 1, ответ равен $$$0$$$.

Во втором наборе входных данных начальные значения здоровья у монстров равны $$$[4, 1, 5, 4, 1, 1]$$$. Одной из оптимальных является следующая последовательность действий:

  • Используя заклинание типа 1, нанести $$$1$$$ единицу урона монстру номер $$$1$$$. Здоровья монстров становятся равны $$$[3, 1, 5, 4, 1, 1]$$$.
  • Используя заклинание типа 1, нанести $$$1$$$ единицу урона монстру номер $$$4$$$. Здоровья монстров становятся равны $$$[3, 1, 5, 3, 1, 1]$$$.
  • Используя заклинание типа 1, снова нанести $$$1$$$ единицу урона монстру номер $$$4$$$. Здоровья монстров становятся равны $$$[3, 1, 5, 2, 1, 1]$$$.
  • Использовать заклинание типа 2:
    • Здоровья монстров становятся равны $$$[2, 0, 4, 1, 0, 0]$$$. Так как монстры номер $$$2$$$, $$$5$$$ и $$$6$$$ умерли, заклинание повторяется.
    • Здоровья монстров становятся равны $$$[1, 0, 3, 0, 0, 0]$$$. Так как монстр номер $$$4$$$ умер, заклинание повторяется.
    • Здоровья монстров становятся равны $$$[0, 0, 2, 0, 0, 0]$$$. Так как монстр номер $$$1$$$ умер, заклинание повторяется.
    • Здоровья монстров становятся равны $$$[0, 0, 1, 0, 0, 0]$$$.
  • Используя заклинание типа 1, нанести $$$1$$$ единицу урона монстру номер $$$3$$$. Здоровья монстров становятся равны $$$[0, 0, 0, 0, 0, 0]$$$.

Всего заклинания типа 1 были применены $$$4$$$ раза. Можно показать, что это наименьшее возможное число.