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

Даны $$$n$$$ башен из кубиков, пронумерованных от $$$1$$$ до $$$n$$$. В $$$i$$$-й башне $$$a_i$$$ кубиков.

За один ход можно переложить один кубик с $$$i$$$-й башни на $$$j$$$-ю, но только если $$$a_i > a_j$$$. Такой ход увеличивает $$$a_j$$$ на $$$1$$$ и уменьшает $$$a_i$$$ на $$$1$$$. Вы можете сделать сколько угодно ходов (возможно, ноль).

Какое наибольшее количество кубиков можно получить на башне $$$1$$$ после ходов?

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

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

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

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — количество кубиков в каждой башне.

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

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

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

Пример
Входные данные
4
3
1 2 3
3
1 2 2
2
1 1000000000
10
3 8 6 7 4 1 2 4 10 1
Выходные данные
3
2
500000001
9
Примечание

В первом наборе входных данных вы можете переместить кубик с башни $$$2$$$ на башню $$$1$$$, сделав количества кубиков равными $$$[2, 1, 3]$$$. Затем переместить кубик с башни $$$3$$$ на башню $$$1$$$, сделав количества кубиков равными $$$[3, 1, 2]$$$. Башня $$$1$$$ высотой $$$3$$$ кубика, и нельзя получить больше.

Во втором наборе входных данных можно переместить кубик с любой из башен $$$2$$$ или $$$3$$$ на башню $$$1$$$ так, чтобы в ней стало $$$2$$$ кубика.

В третьем наборе входных данных можно $$$500000000$$$ раз переместить кубик с башни $$$2$$$ на башню $$$1$$$. После этого количества кубиков станут $$$[500000001, 500000000]$$$.