AT_abc272_g [ABC272G] Yet Another mod M

[problemUrl]: https://atcoder.jp/contests/abc272/tasks/abc272_g 長さ $ 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 $ を出力せよ。

### 制約 - $ 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 $ は条件を満たします。