题目描述

有 $n$ 个积木塔，编号从 $1$ 到 $n$。第 $i$ 个塔有 $a_i$ 个积木。

每次操作，你可以将一个积木从第 $i$ 个塔移动到第 $j$ 个塔，但前提是 $a_i > a_j$。该操作会使 $a_j$ 增加 $1$，$a_i$ 减少 $1$。你可以进行任意多次操作（也可以不操作）。

你能让第 $1$ 个塔最多拥有多少个积木？

输入格式

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

输出格式

对于每个测试用例，输出在进行任意多次操作（也可以不操作）后，第 $1$ 个塔最多能拥有的积木数量。

说明/提示

在第一个测试用例中，你可以将一个积木从第 $2$ 个塔移动到第 $1$ 个塔，此时积木数量为 $[2, 1, 3]$。然后再将一个积木从第 $3$ 个塔移动到第 $1$ 个塔，积木数量变为 $[3, 1, 2]$。此时第 $1$ 个塔有 $3$ 个积木，无法获得更多。

在第二个测试用例中，你可以从第 $2$ 或第 $3$ 个塔移动一个积木到第 $1$ 个塔，使其拥有 $2$ 个积木。

在第三个测试用例中，你可以将 $500000000$ 个积木从第 $2$ 个塔移动到第 $1$ 个塔。之后积木数量为 $[500000001, 500000000]$。

由 ChatGPT 4.1 翻译

样例

4
3
1 2 3
3
1 2 2
2
1 1000000000
10
3 8 6 7 4 1 2 4 10 1

3
2
500000001
9