CF1767B.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 \gt 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?

有 $n$ 座方块塔，编号从 $1$ 到 $n$。第 $i$ 座塔包含 $a_i$ 个方块。

在一次操作中，你可以将一个方块从第 $i$ 座塔移动到第 $j$ 座塔，但前提是必须满足 $a_i \gt a_j$。该操作会使 $a_j$ 增加 $1$，同时使 $a_i$ 减少 $1$。你可以执行任意多次（包括零次）这样的操作。

经过若干次操作后，第 $1$ 座塔上最多能有多少个方块？

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

第一行包含一个整数 $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$。

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

对于每个测试用例，输出在进行任意次数（可能为零次）移动后，塔 $1$ 上所能拥有的最多方块数量。

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

在第一个测试用例中，你可以将一个方块从第 $2$ 座塔移动到第 $1$ 座塔，使得各塔的方块数量变为 $[2, 1, 3]$；然后将一个方块从第 $3$ 座塔移动到第 $1$ 座塔，使得各塔的方块数量变为 $[3, 1, 2]$。此时第 $1$ 座塔拥有 $3$ 个方块，无法再获得更大的数量。

在第二个测试用例中，你可以将一个方块从第 $2$ 或第 $3$ 座塔中的任意一座移动到第 $1$ 座塔，使其拥有 $2$ 个方块。

在第三个测试用例中，你可以将方块从第 $2$ 座塔移动到第 $1$ 座塔，共执行 $500000000$ 次。此后各塔的方块数量将变为 $[500000001, 500000000]$。