Half of Same

题目描述

给定一个包含 $n$（$n$ 是偶数）个整数的数列 $a_1,a_2,\ldots,a_n$。

考虑一个可能的正整数 $k$，在每次操作中，你可以选定一个 $i$，并将 $a_i$ 减少 $k$。

你可以执行任意多次（也可能是零次）操作，使这个数列中至少一半的数相等。

请找出最大的符合条件的 $k$，如果 $k$ 可以是任意的大小，输出 $-1$。

输入格式

本题包含多组数据。

输入的第一行包含一个正整数 $t$，表示数据组数。

每组数据包含两行，其中第一行包含一个偶数 $n$，第二行包含 $n$ 个整数 $a_i,a_2,\ldots,a_n$。

输出格式

对于每组数据，输出一个正整数 $k$ 或 $-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

样例输出

13
2
-1
-1

说明/提示

• $1 \le t \le 10$；
• $4 \le n \le 40$；
• $-10^6 \le a_i \le 10^6$。

保证 $\sum\limits{n} \le 100$。

Translated by @BurningEnderDragon, 2021.10.14