write a go solution for Description:
There are n block towers, numbered from 1 to n. The i-th tower consists of a_i blocks.

In one move, you can move one block from tower i to tower j, but only if a_i>a_j. That move increases a_j by 1 and decreases a_i by 1. You can perform as many moves as you would like (possibly, zero).

What's the largest amount of blocks you can have on the tower 1 after the moves?

Input Format:
The first line contains a single integer t (1<=t<=10^4) — the number of testcases.

The first line of each testcase contains a single integer n (2<=n<=2*10^5) — the number of towers.

The second line contains n integers a_1,a_2,...,a_n (1<=a_i<=10^9) — the number of blocks on each tower.

The sum of n over all testcases doesn't exceed 2*10^5.

Output Format:
For each testcase, print the largest amount of blocks you can have on the tower 1 after you make any number of moves (possibly, zero).

Note:
In the first testcase, you can move a block from tower 2 to tower 1, making the block counts [2,1,3]. Then move a block from tower 3 to tower 1, making the block counts [3,1,2]. Tower 1 has 3 blocks in it, and you can't obtain a larger amount.

In the second testcase, you can move a block from any of towers 2 or 3 to tower 1, so that it has 2 blocks in it.

In the third testcase, you can 500000000 times move a block from tower 2 to tower 1. After that the block countes will be [500000001,500000000].. Output only the code with no comments, explanation, or additional text.