配点 : $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$ を出力せよ。

5
3 17 8 14 10

7

$M=7$ として操作を行うと、$A=(3,3,1,0,3)$ となり $3$ が $A$ の過半数を占めるため $M=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