Migrated from Lutece 3218 生日礼物

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

今天是小u同学的生日，他想要很多生日礼物!

但是他的父母觉得他近期表现欠佳，于是给他画了个饼:

小u的父母一共给出 $n$ 个不同的正整数 $a_1,a_2,\cdots,a_n$

然后让小u自己选一个大于等于 $3$ 的正整数 $m$

这 $n$ 个数会对 $m$ 取模，得到 $b_1,b_2,\cdots,b_n$，设这 $n$ 个数的众数出现次数为 $k$

最后父母会给他买 $k$ 个礼物，因此 $k$ 最终由小u选择的 $m$ 决定

但是小u知道无论他怎么选择正整数 $m$ ，$k$ 的上限是由父母给出的 $n$ 个正整数决定的

而贪心的他想要至少 $\lfloor \frac{n}{2}\rfloor+1$ 个礼物

小u想知道父母有没有坑他，即存不存在 $m$ 使得 $k$ 严格大于 $\lfloor \frac{n}{2}\rfloor$

但是这个问题对他来说还是过于困难，于是请了无所不能的你来帮他解答

如果不存在这个数 $m$，就输出 $-1$，若存在答案，输出满足以上条件最小的 $m$

Input

第一行输入一个数 $n$ ，表示数的个数 第二行输入 $n$ 个数 $a_1,\cdots , a_n$

Output

输出一行一个数，若不存在答案输出 $-1$，若存在则输出满足以上条件最小的 $m$

Samples

5
3 17 8 14 10

3

10
1 2 3 4 5 6 7 8 9 10

-1

Constraints

$3 \leq n \leq 5000$ $1 \leq a_i \leq 10^9$

Note

样例1解释: 取模后的新数组为 $(0,2,2,2,1)$，$2$ 为众数出现了 $3$ 次，严格大于 $\lfloor \frac{5}{2} \rfloor = 2$ 没有更小的数满足条件