环顾四周,富人越来越富,穷人越来越穷。我们需要向富人索取并给予穷人。我们需要罗宾汉!
镇上居住着 $$$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$$$人不快乐。