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<y)$，将这对球上的数字分别改为 $x+0.5,y-0.5$。

执行完操作后，令 $d$ 为写有相同数字的球的个数的最大值。求 $d$ 的最小可能值。

多组数据。

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