给定 $n$ ($n$ 为偶数)个整数数组 $a_1,a_2,\dots,a_n$
考虑这样的一个 $k$,每次操作选定一个 $i$,将 $a_i$ 减少 $k$,执行多次(可能 $0$ 次)后使得数组中至少有一半的元素相等,求最大的 $k$,如果这样的 $k$ 为无穷大,输出 $-1$
输入格式
输入包含两行,第一行为一个正整数 $n$,表示数组大小。第二行为 $n$ 个整数 $a_1,a_2,\dots,a_n$
输出格式
输出题意中的 $k$
样例输入
8
-1 0 1 -1 0 1 -1 0
样例输出
2
数据规模
$4\leq n \leq 100$,数据保证 $n$ 为偶数
$-10^6\leq a_i \leq 10^6$