Background

Little Z is going to run. He wants to outpace his classmates after school starts.

Problem Description

Little Z is running on a road. There are $n$ supermarkets on the road, and the position of the $i$-th supermarket is $a_i$. When the time at which Little Z passes a supermarket is odd, he will go shopping there, and then he will be outpaced by his classmates.

Little Z starts at position $0$. Every unit of time, he runs $v$ units to the right.

You need to find the maximum value of $v$ such that, when Little Z passes each of the $n$ supermarkets, he never goes shopping.

It is required that $v$ must be a positive integer, and the time Little Z spends to reach any supermarket must be an integer. In other words, you need to ensure that the time when Little Z reaches any supermarket is even. Note that the initial time is $0$.

Input Format

The input has $n+1$ lines.

Line $1$ contains one positive integer $n$.

Lines $2$ to $n+1$ each contain one positive integer. The positive integer in line $i+1$ is $a_i$.

Output Format

The output has $1$ line.

Output the maximum $v$ that satisfies the conditions. If there is no solution, output $-1$.

2
1 
2

-1

5
10 
20 
30
40
50

5

Hint

Sample Explanation

For sample $1$, it can be proven that there is no speed that meets the requirements.

For sample $2$, when $v=5$, the times to reach supermarkets $1$ to $5$ are $2$, $4$, $6$, $8$, $10$, all of which are even, so the requirement is satisfied. It can be proven that there is no faster valid speed.

This problem uses bundled testdata.

For $100\%$ of the data, $1 \le n \le 2\times10^6$, $1\le a_1<a_2<\dots<a_{n-1}<a_n\le3\times10^{18}$. It is guaranteed that all inputs are positive integers.

Translated by ChatGPT 5