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 \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

题目描述

This problem is a complicated version of D1, but it has significant differences, so read the whole statement. Polycarp has an array of $ n $ ( $ n $ is even) integers $ a_1, a_2, \dots, a_n $ . Polycarp conceived of a positive integer $ k $ . After that, Polycarp began performing the following operations on the array: take an index $ i $ ( $ 1 \le i \le n $ ) and reduce the number $ a_i $ by $ k $ . After Polycarp performed some (possibly zero) number of such operations, it turned out that at least half of the numbers in the array became the same. Find the maximum $ k $ at which such a situation is possible, or print $ -1 $ if such a number can be arbitrarily large.

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 10 $ ) — the number of test cases. Then $ t $ test cases follow. Each test case consists of two lines. The first line contains an even integer $ n $ ( $ 4 \le n \le 40 $ ) ( $ n $ is even). The second line contains $ n $ integers $ a_1, a_2, \dots a_n $ ( $ -10^6 \le a_i \le 10^6 $ ). It is guaranteed that the sum of all $ n $ specified in the given test cases does not exceed $ 100 $ .

输出格式

For each test case output on a separate line an integer $ k $ ( $ k \ge 1 $ ) — the maximum possible number that Polycarp used in operations on the array, or $ -1 $ , if such a number can be arbitrarily large.

输入输出样例

输入样例 #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