整齐的数组2

题目描述

​ Polycarp 有一个长度为 $n$ 的数组 $a_1,a_2,...,a_n$（$n$ 是偶数）。Polycarp 还得到了一个正整数 $k$，他开始对数组 $a$ 做如下操作：选择一个下标 $i\ (1 \leq i \leq n)$ 使 $a_i$ 减去 $k$。

​ 在 Polycarp 进行若干次操作后（可能 $0$ 次），数组 $a$ 中的数至少有一半都变成相同的了。请你找到最大的符合要求的 $k$，如果 $k$ 可以为任意大，请输出 $-1$。

输入格式

​ 第一行一个整数 $t$，表示测试单元的个数。

​ 接下来每个测试单元有两行。第一行包含一个偶数 $n$。第二行包含 n 个整数 $a_1, a_2,...,a_n$。

输出格式

​ 对于每个测试单元输出单独一行一个整数 $k\ (k\geq 1)$ —— Polycarp 能用来对数组进行操作的最大的数，或者 $-1$ —— 如果 $k$ 能任意大的话。

样例输入

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 \leq t \leq 10$，$4\leq n\leq 40$（$n$ 是偶数），$-10^6 \leq a_i\leq 10^6$，并且 n 的总和不超过100。