I. Abu Tahun Mod problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Abu Tahun loves palindromes.

An array is palindrome if it reads the same backwards and forwards, for example arrays $\{1\}$, $\{1,1,1\}$, $\{1,2,1\}$ , $\{1,3,2,3,1\}$ are palindrome, but arrays $\{11,3,5,11\}$, $\{1,12\}$ are not.

Abu Tahun has an array of $n$ integers $A$. He wants his array to be palindrome. He can choose an integer $m$, then change the value of all $A_i$ $(1 \leq i \leq n)$ to ($A_i\mod m$).

what is the maximum value of $m$ he can choose, such that the array becomes palindrome?

Input

The first line of input contains a single integer $n$ $( 1 \leq n \leq 10^{5})$

The second line contains integers $A_1$,$A_2$,...,$A_n$ $(1 \leq A_i \leq 10^{9})$

Output

Print the maximum value of $m$ Abu Tahun can choose, if $m$ is arbitrarily large print -1.

Examples
Input
4
1 1 1 1

Output
-1
Input
4
1 2 3 4

Output
1

Input
3
8 12 16

Output
8