Problem Statement

There are $N$ piles of stones, and the $i$-th pile ($1 \leq i \leq N$) has $A_i$ stones.

You will choose a positive integer $k$. Then, Alice and Bob will play a game with these piles as follows.

• Starting with Alice, the players take turns to play.
• In each turn, the player must choose a non-empty pile and remove from it some number of stones between $1$ and $k$, inclusive.

The person who cannot make a move on their turn loses, and the other person wins.

You want to choose a positive integer $k$ for which there is a winning strategy for Alice. Determine if such a $k$ exists. If it exists, determine if there is a maximum value for such $k$. If the maximum value exists, provide that value.

Constraints

• $1 \leq N \leq 250000$
• $1 \leq A_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

If there is no $k$ for which Alice has a winning strategy, print $0$.

If there is a $k$ for which Alice has a winning strategy, and there is no maximum value for such $k$, print $-1$.

If there is a $k$ for which Alice has a winning strategy, and there is a maximum value for such $k$, print that value.