题目描述

長さ $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$ の個数より多いことを言います。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

条件を満たす $M$ が存在するのであればそのような $M$ を $1$ 個出力せよ。そうでないならば $-1$ を出力せよ。

题目大意

给出一个长度为 $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$。

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$ の全ての要素は相異なる
• 入力はすべて整数

Sample Explanation 1

$M=7$ として操作を行うと、$A=(3,3,1,0,3)$ となり $3$ が $A$ の過半数を占めるため $M=7$ は条件を満たします。