Yet Another mod M

题目描述

给你一个长度为 $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_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

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$ 的元素两两互不相同。 输入中的所有数值均为整数。如果取 $M=7$ 进行操作，你将得到 $A=(3,3,1,0,3)$，其中 $3$ 在 $A$ 中是多数元素，因此 $M=7$ 满足条件。

标签: AtCoder|abc272G

来源

AtCoder|abc272G