CF2140F.Sum Minimisation

给定一个长度为 $n$ 的数组 $a$，你可以对数组 $a$ 执行如下操作任意次（包括零次）：

1. 任意选择 $k$ 个不同的下标组成集合 $S = \{i_1, i_2, \ldots, i_k\}$，其中 $1 \le i_j \le n$，对于所有 $1 \le j \le k$。
2. 计算 $x = a_{i_1} + a_{i_2} + \cdots + a_{i_k}$，然后设 $y = x - \left\lfloor \frac{x}{k} \right\rfloor \cdot k$。
3. 在选中的元素 $a_{i_1}, \ldots, a_{i_k}$ 中，对其中 $y$ 个最小的值各减少 $1$。
   • 如果两个元素值不同（$a_i \ne a_j$），值较小者为更小的元素。
   • 如果两个元素值相同（$a_i = a_j$），下标较小者为更小的元素。
   • 如果 $y=0$，则不减少任何元素。

你的任务是，在任意次数操作之后，求数组 $a$ 所有元素之和能达到的最小可能值，或者判断是否能够无限减少。

每个测试点包含多组测试数据。第一行给出测试用例数 $t$（$1 \le t \le 10^4$）。
接下来每组测试数据：
第一行包含一个整数 $n$（$1 \le n \le 10^6$），表示数组 $a$ 的长度。
第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le 10^9$），表示数组 $a$ 的元素。

保证所有测试数据中 $n$ 的总和不超过 $10^6$。

对于每个测试用例，输出一行，表示执行上述操作若干次后，数组 $a$ 的元素和可以达到的最小值。

如果数组元素和能被无限减少，输出 $-1$。

在第一个测试点中，我们只能对整个数组操作一次，最终可以得到 $a = [2,0]$，之后无法再进行操作使其和减少。

在第二个测试点中，无法通过任何操作减少和，因此答案为数组元素之和。

在第三个测试点中，存在一系列操作可以使数组总和无限减少。

由 ChatGPT 5 翻译