Block Towers
Contest: Educational Codeforces Round 140 (Rated for Div. 2)
Difficulty rating: 800
Tags: data structures, greedy, sortings

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

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
4
3
1 2 3
3
1 2 2
2
1 1000000000
10
3 8 6 7 4 1 2 4 10 1

Example output:
3
2
500000001
9

Editorial:
Notice that it never makes sense to move blocks between the towers such that neither of them is tower $$$1$$$ as that can only decrease the heights. Moreover, it never makes sense to move blocks away from the tower $$$1$$$. Thus, all operations will be moving blocks from some towers to tower $$$1$$$.
At the start, which towers can move at least one block to tower $$$1$$$? Well, only such $$$i$$$ that $$$a_i > a_1$$$. What happens after you move a block? Tower $$$1$$$ becomes higher, some tower becomes lower. Thus, the set of towers that can share a block can't become larger.
Let's order the towers by the number of blocks in them. At the start, the towers that can share a block are at the end (on some suffix) in this order. After one move is made, the towers get reordered, and the suffix can only shrink.
Ok, but if that suffix shrinks, what's the first tower that will become too low? The leftmost one that was available before. So, regardless of what the move is, the first tower that might become unavailable is the leftmost available tower. Thus, let's attempt using it until it's not too late.
The algorithm then is the following. Find the lowest tower that can move the block to tower $$$1$$$, move a block, repeat. When there are no more towers higher than tower $$$1$$$, the process stops.
However, the constraints don't allow us to do exactly that. We'll have to make at most $$$10^9$$$ moves per testcase.
Ok, let's move the blocks in bulk every time. Since the lowest available tower will remain the lowest until you can't use it anymore, make all the moves from it at the same time. If the current number of blocks in tower $$$1$$$ is $$$x$$$ and the current number of blocks in that tower is $$$y$$$, $$$\lceil\frac{y - x}{2}\rceil$$$ blocks can be moved.
You can also avoid maintaining the available towers by just iterating over the towers in the increasing order of their height.
Overall complexity: $$$O(n \log n)$$$ per testcase.