该问题是 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