A15656. Block Towers

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?

The first line contains a single integer $t$ ( $1 \le t \le 10^4$ ) — the number of testcases.

The first line of each testcase contains a single integer $n$ ( $2 \le n \le 2 \cdot 10^5$ ) — the number of towers.

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

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

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).

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]$ .