Half Equal

Problem Description

You are given an array $a_1, a_2, \dots, a_n$ of $n$ integers ($n$ is even).

Consider such a $k$. In one operation you choose an index $i$ and decrease $a_i$ by $k$. After performing several operations (possibly $0$), at least half of the elements in the array become equal. Find the largest such $k$; if $k$ can be arbitrarily large, output $-1$.

Input Format

The input consists of two lines. The first line is a positive integer $n$, the size of the array. The second line contains $n$ integers $a_1, a_2, \dots, a_n$.

Output Format

Output the $k$ described in the problem statement.

Sample Input

8
-1 0 1 -1 0 1 -1 0

Sample Output

2

Constraints

$4 \leq n \leq 100$, it is guaranteed that $n$ is even.

$-10^6 \leq a_i \leq 10^6$.