102726: [AtCoder]ABC272 G - Yet Another mod M
Description
Score : $600$ points
Problem Statement
You are given a sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$ consisting of positive integers, where the elements of $A$ are distinct.
You will choose a positive integer $M$ between $3$ and $10^9$ (inclusive) to perform the following operation once:
- For each integer $i$ such that $1 \le i \le N$, replace $A_i$ with $A_i \bmod M$.
Can you choose an $M$ so that $A$ satisfies the following condition after the operation? If you can, find such an $M$.
- There exists an integer $x$ such that $x$ is the majority in $A$.
Here, an integer $x$ is said to be the majority in $A$ if the number of integers $i$ such that $A_i = x$ is greater than the number of integers $i$ such that $A_i \neq x$.
Constraints
- $3 \le N \le 5000$
- $1 \le A_i \le 10^9$
- The elements of $A$ are distinct.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ $\dots$ $A_N$
Output
If there exists an $M$ that satisfies the condition, print such an $M$. Otherwise, print $-1$.
Sample Input 1
5 3 17 8 14 10
Sample Output 1
7
If you let $M=7$ to perform the operation, you will have $A=(3,3,1,0,3)$, where $3$ is the majority in $A$, so $M=7$ satisfies the condition.
Sample Input 2
10 822848257 553915718 220834133 692082894 567771297 176423255 25919724 849988238 85134228 235637759
Sample Output 2
37
Sample Input 3
10 1 2 3 4 5 6 7 8 9 10
Sample Output 3
-1
Input
题意翻译
给出一个长度为 $N$ 的序列 $A$， 其中 $A$ 的每个元素均为正整数且互不相同。 你需要选择一个的正整数 $M$，满足 $3\leq M\leq 10^9$，并执行一次下列操作： - 对于 $1\leq i\leq N$，将 $A_i$ 替换为 $A_i$ $mod$ $M$。 若能找到一个数 $M$ 使得序列 $A$ 中存在一个数 $x$，且对于 $1\leq i\leq N$，满足 $A_i=x$ 的数量大于 $A_i$ $ \mathrlap{\,/}{=}$ $ x$ 的数量，输出这个 $M$，否则输出 $-1$。Output
问题描述
给你一个长度为$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$中的多数元素。
约束条件
- $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