← 返回题目列表

Codeforces · 1538/B

B. 朋友和糖果

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

Polycarp 有 $$$n$$$ 个朋友,他的第 $$$i$$$ 个朋友有 $$$a_i$$$ 糖果。坡旅甲的朋友们不喜欢他们拥有不同数量的糖果。换句话说,他们希望所有 $$$a_i$$$ 都相同。为了解决这个问题,Polycarp 仅执行一次以下一组操作:

- Polycarp 选择 $$$k$$$ ($$$0 \le k \le n$$$) 个任意朋友(假设他选择索引为 $$$i_1, i_2, \ldots, i_k$$$ 的朋友);
- Polycarp 将他们的 $$$a_{i_1} + a_{i_2} + \ldots + a_{i_k}$$$ 糖果分发给所有 $$$n$$$ 朋友。在分配每个 $$$a_{i_1} + a_{i_2} + \ldots + a_{i_k}$$$ 糖果时,他会选择新的所有者。这可以是任何 $$$n$$$ 朋友。请注意,任何糖果都可以给予在分发过程之前拥有该糖果的人。

注意,数字$$$k$$$不是预先固定的,可以是任意的。您的任务是找到 $$$k$$$ 的最小值。

例如,如果 $$$n=4$$$ 且 $$$a=[4, 5, 2, 5]$$$,则 Polycarp 可以进行以下糖果分配:

- Polycarp 选择 $$$k=2$$$ 索引为 $$$i=[2, 4]$$$ 的朋友,并分发 $$$a_2 + a_4 = 10$$$ 糖果来制作 $$$a=[4, 4, 4, 4]$$$ (两颗糖果送给 $$$3$$$ 人)。

请注意,在这个例子中,Polycarp 无法选择 $$$k=1$$$ 朋友,以便他可以重新分配糖果,以便最终所有 $$$a_i$$$ 都是相等的。

对于数据$$$n$$$ 和$$$a$$$,确定最小值$$$k$$$。有了这个值 $$$k$$$,Polycarp 应该能够选择 $$$k$$$ 朋友并重新分配他们的糖果,以便每个人最终都会得到相同数量的糖果。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$)。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^4$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例输出:

- $$$k$$$的最小值,这样Polycarp可以准确地选择$$$k$$$朋友,这样他就可以按照想要的方式重新分配糖果;
- 如果不存在这样的值 $$$k$$$,则为“-1”。

示例

输入 #1

5
4
4 5 2 5
2
0 4
5
10 8 5 1 4
1
10000
7
1 1 1 1 1 1 1

输出 #1

2
1
-1
0
0