問題文

長さ $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