AT_abc272_g.[ABC272G] Yet Another mod M

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

你可以选择一个满足 $3 \leq M \leq 10^9$ 的正整数 $M$，并进行以下操作一次：

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

你能否通过巧妙地选择 $M$，使得操作后的 $A$ 满足以下条件？如果可以，请给出一个满足条件的 $M$。

• 存在某个整数 $x$，使得 $x$ 在 $A$ 中占据了多数。

这里，“$x$ 在 $A$ 中占据多数”指的是，满足 $A_i = x$ 的 $i$ 的个数严格多于满足 $A_i \neq x$ 的 $i$ 的个数。

输入通过标准输入给出，格式如下：

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

如果存在满足条件的 $M$，请输出其中一个 $M$。如果不存在，请输出 $-1$。

限制

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

样例解释 1

当 $M=7$ 时，操作后 $A=(3,3,1,0,3)$，此时 $3$ 在 $A$ 中占据多数，因此 $M=7$ 满足条件。

由 ChatGPT 4.1 翻译