又一个模 M 问题

题目描述

给你一个长度为 $N$、由正整数组成且元素互不相同的序列 $A=(A_1,A_2,\dots,A_N)$。

你将选择一个满足 $3 \le M \le 10^9$ 的正整数 $M$,并执行一次以下操作:

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

能否选择这样的 $M$,使得操作后 $A$ 满足以下条件?如果可以,求出这样的 $M$。

存在一个整数 $x$,使得 $x$ 是 $A$ 中的多数。

这里,如果满足 $A_i = x$ 的整数 $i$ 的个数大于满足 $A_i \neq x$ 的整数 $i$ 的个数,则称整数 $x$ 是 $A$ 中的多数。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

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

样例

5
3 17 8 14 10

7

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

10
822848257 553915718 220834133 692082894 567771297 176423255 25919724 849988238 85134228 235637759

37

10
1 2 3 4 5 6 7 8 9 10

-1

数据范围

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