题目描述

给定一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\dots,A_N)$，其中 $A$ 的元素都是不同的。

你将选择一个大于等于 $3$ 且小于等于 $10^9$ 的正整数 $M$ 来执行以下操作：

• 对于每一个满足 $1 \le i \le N$ 的整数 $i$，将 $A_i$ 替换为 $A_i \bmod M$。

能否选择一个 $M$，使得在操作之后 $A$ 满足以下条件？如果可以，请找到这样的 $M$。

• 存在一个整数 $x$，使得 $x$ 是 $A$ 中的多数元素。

这里，$A$ 中的多数元素指的是满足 $A_i = x$ 的整数 $i$ 的个数大于满足 $A_i \neq x$ 的整数 $i$ 的个数。

约束条件

• $3 \le N \le 5000$
• $1 \le A_i \le 10^9$
• $A$ 中的元素都不相同。
• 输入中的所有值都是整数。

输入

输入从标准输入中以以下格式给出：

$N$ $A_1$ $A_2$ $\dots$ $A_N$

输出

如果存在满足条件的 $M$，请输出这样的 $M$。否则，输出 $-1$。

示例输入 1

5
3 17 8 14 10

示例输出 1

7

如果你选择 $M=7$ 来执行操作，你将得到 $A=(3,3,1,0,3)$，其中 $3$ 是 $A$ 中的多数元素，所以 $M=7$ 满足条件。

示例输入 2

10
822848257 553915718 220834133 692082894 567771297 176423255 25919724 849988238 85134228 235637759

示例输出 2

37

示例输入 3

10
1 2 3 4 5 6 7 8 9 10

示例输出 3

-1