AT_awtf2025_c Get Closer

有一些球上面写着 $1$ 到 $N$ 的整数。有 $A_i$ 个球上写着 $i$。 令 $S=A_1+A_2+\cdots+A_N$，保证 $S$ 是一个正偶数。你要把 $S$ 个球划分成 $S/2$ 对，要求每一对的两个球上写的数字不同。可以证明在本题的数据范围内一定存在划分方案。 对于每对球，执行以下操作： - 设这对球上的两个数字是 $x,y(x

第一行一个整数 $T$，表示数据组数。 对于每组数据，第一行一个整数 $N$。 第二行 $N$ 个整数 $A_1,A_2,\cdots,A_N$。

对于每组数据，输出一行一个整数表示答案。

**数据范围** - $1\le T\le 1.25\times 10^5$ - $2\le N \le 2.5\times 10^5$ - $0\le A_i\le 10^9$ - $S=A_1+A_2+\cdots+A_N$ 是一个正偶数。 - $A_i\le S/2$ - 保证单个测试点中 $N$ 的和不超过 $2.5\times 10^5$。 - 所有输入均为整数。 **样例解释** 对于第一组数据，我们令 $(x,y)$ 表示一对球，分别写有 $x,y$。 如果我们分组为 $(1,3),(2,3),(2,4)$，操作后球上的数字为 $1.5,2.5,2.5,2.5,2.5,3.5$，写有相同数字的球的个数的最大值 $d=4$。 考虑另一种情况，如果我们分组为 $(1,2),(2,3),(3,4)$，操作后球上的数字为 $1.5,1.5,2.5,2.5,3.5,3.5$，写有相同数字的球的个数的最大值 $d=2$。 $d$ 不可能小于 $2$，所以答案是 $2$。