← 返回题目列表

Codeforces · 2140/F

F. 总和最小化

中文机器翻译题面 查看原题

给定一个大小为 $$$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,a_3,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,打印执行上述操作任意次数后可以达到的数组 $$$a$$$ 元素总和的最小可能值。

如果数组 $$$a$$$ 的元素总和可以无限减少,则打印 $$$-1$$$。

示例

输入
复制

3
2
2 1
4
3 3 3 3
8
1 2 3 4 5 6 7 8

输出
复制

2
12
-1

注意

在第一个测试用例中,我们只能对整个数组执行一次操作,这会导致数组 $$$a = [2, 0]$$$,之后任何操作都不会导致数组减少。

在第二个测试用例中,没有任何操作会导致减少,因此,答案是给定数组元素的总和。

在第三个测试用例中,存在一系列操作,允许我们无限期地减少数组元素的总和。