/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。ここで A の全ての要素は相異なります。
あなたは 3 以上 10^9 以下の正整数 M を選び、以下の操作を 1 回だけ行います。
- 1 \le i \le N を満たす整数 i に対し、A_i を A_i \bmod M で置き換える。
うまく M を選ぶことで、操作後の A を以下の条件を満たした状態にすることができますか？ できるのであれば、そのような M を 1 個求めてください。
- ある整数 x が存在して、x が A の過半数を占める。
ここで、整数 x が A の過半数を占めるとは、A_i = x を満たす整数 i の個数が A_i \neq x を満たす i の個数より多いことを言います。
制約
- 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 を出力せよ。
入力例 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
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