← 返回题目列表

Codeforces · 1593/D2

D2. 一半相同

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

该问题是 D1 的复杂版本,但有显着差异,因此请阅读整个陈述。

Polycarp 有一个 $$$n$$$ 数组($$$n$$$ 是偶数)整数 $$$a_1, a_2, \dots, a_n$$$。波利卡普设想了一个正整数$$$k$$$。之后,Polycarp 开始对数组执行以下操作:获取索引 $$$i$$$ ($$$1 \le i \le n$$$) 并将数字 $$$a_i$$$ 减少 $$$k$$$。

在Polycarp执行了一些(可能是零)次这样的操作之后,结果发现数组中至少有一半的数字变得相同。找到可能出现这种情况的最大$$$k$$$,或者如果这个数字可以任意大,则打印$$$-1$$$。

输入

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

每个测试用例由两行组成。第一行包含一个偶数 $$$n$$$ ($$$4 \le n \le 40$$$) ($$$n$$$ 是偶数)。第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots a_n$$$ ($$$-10^6 \le a_i \le 10^6$$$)。

保证给定测试用例中指定的所有 $$$n$$$ 的总和不超过 $$$100$$$。

输出

对于每个测试用例在单独的行上输出一个整数 $$$k$$$ ($$$k \ge 1$$$) — Polycarp 在数组操作中使用的最大可能数字,或 $$$-1$$$(如果这个数字可以任意大)。

示例

输入 #1

4
6
48 13 22 -15 16 35
8
-1 0 1 -1 0 1 -1 0
4
100 -1000 -1000 -1000
4
1 1 1 1

输出 #1

13
2
-1
-1