C. Смайло и монстры
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мальчик Смайло играет в новую игру! В игре есть $$$n$$$ орд монстров, в $$$i$$$-й орде $$$a_i$$$ монстров. Цель игры — уничтожить всех монстров. Для этого у вас есть два типа атак и счетчик комбо $$$x$$$, изначально равный $$$0$$$:

  • Первый тип атаки: вы выбираете число $$$i$$$ от $$$1$$$ до $$$n$$$ такое, что в орде с номером $$$i$$$ остался хотя бы один монстр. Затем вы убиваете одного монстра из орды с номером $$$i$$$, и счетчик комбо $$$x$$$ увеличивается на $$$1$$$.
  • Второй тип атаки: вы выбираете число $$$i$$$ от $$$1$$$ до $$$n$$$ такое, что в орде с номером $$$i$$$ осталось хотя бы $$$x$$$ монстров. Затем вы применяете ультимейт и убиваете $$$x$$$ монстров из орды под номером $$$i$$$. После этого $$$x$$$ обнуляется.

Ваша задача — зачистить всех монстров, то есть сделать так, чтобы ни в одной орде не осталось ни одного монстра. Смайло хочет как можно скорее победить, поэтому скажите, какое минимальное число атак можно применить?

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

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — количества монстров в каждой орде.

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

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

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

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

В первом наборе входных данных можно применить атаку первого типа по одному разу на $$$1$$$-ю, $$$3$$$-ю и $$$4$$$-ю орду, затем добить атакой второго типа $$$2$$$-ю орду. Итого нужно $$$4$$$ атаки.

Во втором наборе входных данных можно применить атаку первого типа по одному разу на $$$1$$$-ю, $$$3$$$-ю орду, затем добить атакой второго типа $$$2$$$-ю орду, затем применить атаку первого типа один раз на $$$4$$$-ю орду. Итого нужно $$$4$$$ атаки.

В четвёртом наборе входных данных можно применить атаку первого типа один раз на $$$1$$$-ю орду, два раза на $$$2$$$-ю орду, затем применить один раз атаку второго типа на $$$2$$$-ю орду, затем применить один раз атаку первого типа на $$$2$$$-ю орду. Итого нужно $$$5$$$ атак.