D. Наездник на курице
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Стив по глупости стал копать ночью и наткнулся на монструозное существо: наездника на курице$$$^n$$$!

Наездник на курице$$$^n$$$ состоит из $$$n$$$ мобов, поставленных по порядку друг на друга; моб $$$1$$$ находится внизу, а моб $$$n$$$ — на самом верху. У моба $$$i$$$ изначально $$$h_i$$$ здоровья.

За одну атаку Стив может нанести $$$1$$$ урон любому мобу. Если любой моб достигает $$$0$$$ или менее здоровья, он умирает, и все мобы сверху него падают вниз и формируют новую стопку. Моб, находящийся внизу новой стопки, получает $$$1$$$ урон от падения за каждого моба, который был ниже его до падения (включая того, который только что умер). Это также может его убить, в этом случае все мобы сверху него снова падают вниз, и процесс повторяется.

Например, рассмотрим наездника на курице$$$^6$$$ с начальными значениями здоровья мобов $$$[1, 2, 1, 3, 5, 2]$$$. Если Стив повредит третьего моба в стопке, он умирает, и мобы со здоровьем $$$[3, 5, 2]$$$ падают вниз в новую стопку. Нижний моб получает $$$3$$$ единицы урона от падения, поэтому он также умирает, и мобы со здоровьем $$$[5, 2]$$$ падают вниз в новую стопку. Нижний моб получает $$$1$$$ единицу урона от падения. В итоге, после первой атаки Стива будет две стопки со здоровьем $$$[1, 2]$$$ и $$$[4, 2]$$$.

Меч Стива не зачарован на починку, поэтому он хочет узнать минимальное количество атак, необходимое для уничтожения всех мобов.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$h_1, h_2,\ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$) — начальное здоровье каждого моба.

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

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

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

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

В первом наборе входных данных начальная стопка имеет мобов со здоровьем $$$[3, 1, 4, 1, 2]$$$. Стив может использовать одну атаку, чтобы повредить второго моба в стопке и убить его. Третий моб получает $$$2$$$ единицы урона от падения. Теперь есть две стопки: $$$[3]$$$ и $$$[2, 1, 2]$$$. Стив может убить второго моба во второй стопке. Третий моб в стопке получает $$$2$$$ единицы урона от падения, убивая его. Теперь есть две стопки: $$$[3]$$$ и $$$[2]$$$. Наконец, Стив может использовать пять атак, чтобы убить оставшихся мобов.

Во втором наборе входных данных Стив может нанести $$$1$$$ урон нижнему мобу в стопке. Когда он умирает, второй моб получает $$$1$$$ единицу урона от падения и умирает; затем третий моб получает $$$1$$$ единицу урона от падения и умирает; наконец, четвертый моб получает $$$1$$$ единицу урона от падения и умирает.