Problem Background

It is recommended to use a faster input method.

Xiao Z plans to go running and wants to outperform his classmates after school starts.

Problem Description

Xiao Z is running on a highway where there are \( n \) supermarkets, with the \( i \)-th supermarket located at position \( a_i \). When Xiao Z passes a supermarket at an odd time, he will go shopping, thus being outperformed by his classmates.

Xiao Z starts at the position \( 0 \). He will run \( v \) units to the right every unit of time.

You are asked to find the maximum value of \( v \) such that Xiao Z does not go shopping at any of the \( n \) supermarkets.

The value of \( v \) must be a positive integer, and the time Xiao Z reaches any supermarket must be an integer. In other words, you need to ensure that the time Xiao Z reaches any supermarket is even. Note that the initial time is \( 0 \).

Input Format

The input consists of \( n+1 \) lines.

The first line contains one positive integer \( n \).

Lines \( 2 \) to \( n+1 \) each contain one positive integer, where the \( i+1 \)-th line contains the integer \( a_i \).

Output Format

The output consists of one line.

Output the maximum value of \( v \) that meets the conditions. If there is no solution, output \( -1 \).

Sample Input and Output

Sample Input #1

2
1
2

Sample Output #1

-1

Sample Input #2

5
10
20
30
40
50

Sample Output #2

5

Notes

Sample Explanation

For Sample #1, it can be proven that no speed meets the requirements.

For Sample #2, when \( v = 5 \), the times to reach the 1st to 5th supermarkets are \( 2 \), \( 4 \), \( 6 \), \( 8 \), and \( 10 \), all of which are even, meeting the requirements of the problem. It can be proven that no faster speed meets the requirements.

This problem uses batched testing.

For \( 100\% \) of the data, \( 1 \le n \le 2 \times 10^6 \), \( 1 \le a_1 < a_2 < \dots < a_{n-1} < a_n \le 3 \times 10^{18} \). All inputs are positive integers.

见题面 Input 部分

见题面 Output 部分