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$。

输入输出样例 #1

输入 #1

5
3 17 8 14 10

输出 #1

7

输入输出样例 #2

输入 #2

10
822848257 553915718 220834133 692082894 567771297 176423255 25919724 849988238 85134228 235637759

输出 #2

37

输入输出样例 #3

输入 #3

10
1 2 3 4 5 6 7 8 9 10

输出 #3

-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 翻译