← 返回题目列表

Codeforces · 2014/C

C. 镇上的罗宾汉

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

环顾四周,富人越来越富,穷人越来越穷。我们需要向富人索取并给予穷人。我们需要罗宾汉!

镇上居住着 $$$n$$$ 人。刚才第$$$i$$$人的财富是$$$a_i$$$黄金。但你猜怎么着?首富又发现了额外的第一桶金!

更正式地说,找到 $$$a_j=max(a_1, a_2, \dots, a_n)$$$,将 $$$a_j$$$ 更改为 $$$a_j+x$$$,其中 $$$x$$$ 是锅中找到的黄金的非负整数。如果有多个最大值,则可以是其中任意一个。

如果一个人的财富严格低于平均财富$$$^{\text{*}}$$$的一半,他就会不快乐。

如果严格来说超过一半的总人口 $$$n$$$ 不高兴,罗宾汉就会应大众的要求出现。

确定罗宾汉出现的$$$x$$$的最小值,如果不可能则输出$$$-1$$$。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — 总人口。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) - 每个人的财富。

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

输出

对于每个测试用例,输出一个整数——最富有的人必须找到罗宾汉出现的最少黄金数量。如果不可能,则输出$$$-1$$$。

示例

输入 #1

6
1
2
2
2 19
3
1 3 20
4
1 2 3 4
5
1 2 3 4 5
6
1 2 1 1 1 25

输出 #1

-1
-1
0
15
16
0

注意

在第一个测试用例中,一个人不可能不快乐。

在第二个测试用例中,总是有 $$$1$$$ 快乐的人(最富有的人)。

在第三个测试用例中,不需要额外的金币,所以答案是$$$0$$$。

在第四个测试用例中,添加$$$15$$$黄金后,平均财富变为$$$\frac{25}{4}$$$,而这个平均值的一半为$$$\frac{25}{8​​}$$$,导致$$$3$$$的人不快乐。

第五个测试用例中,添加$$$16$$$黄金后,平均财富变为$$$\frac{31}{5}$$$,导致$$$3$$$人不快乐。