CF 1767B - Block Towers

There are n block towers, numbered from 1 to n. The i-th tower consists of ai blocks.

In one move, you can move one block from tower i to tower j, but only if ai>aj. That move increases aj by 1 and decreases ai 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

The first line contains a single integer t (1≤t≤104) — the number of testcases.

The first line of each testcase contains a single integer n (2≤n≤2⋅105) — the number of towers.

The second line contains n integers a1,a2,…,an (1≤ai≤109) — the number of blocks on each tower.

The sum of n over all testcases doesn't exceed 2⋅105.

Output

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

-------------------------------------------------------------

有n座塔楼，编号从1到n。 第 i 座塔由 ai 块组成。

一次移动，您可以将一个方块从 i 塔移动到 j 塔，但前提是 ai>aj。 该移动使 aj 增加 1，并将 ai 减少 1。您可以执行任意数量的移动（可能是零）。

移动后 1 号塔上最多可以拥有多少块方块？

输入

第一行包含一个整数 t (1≤t≤104) — 测试用例的数量。

每个测试用例的第一行包含一个整数 n (2≤n≤2⋅105) — 塔的数量。

第二行包含 n 个整数 a1,a2,…,an (1≤ai≤109) — 每个塔上的块数。

所有测试用例的 n 总和不超过 2⋅105。

输出

对于每个测试用例，在进行任意次数的移动（可能为零）后，打印塔 1 上可以拥有的最大块数。

----------------------------

只要先找跟a1最接近的值，然后把a1增加后，在继续找，所以这里面可以用排序解决，但是我用数组排序，提交后，超时了。。。没办法就只能有优先队列了。还好通过了。。

下面是代码：