一半相等

题目描述

给定 $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$