Equal GCD Partition

Given a positive integer ( n ) and an array ( a ) of ( n ) positive integers, partition the array into two subsets ( B ) and ( C ), and choose a positive integer ( x ) (with ( 1 \le x \le 10^9 )) such that [ \sum_{y \in B} \gcd(x,y) = \sum_{y \in C} \gcd(x,y). ] If no solution exists, output ( -1 ).

The problem guarantees that if a solution exists, there is one with ( x \le 10^9 ).

inputFormat

The input consists of two lines. The first line contains a single positive integer ( n ). The second line contains ( n ) positive integers ( a_1, a_2, \dots, a_n ) separated by spaces.

outputFormat

Output a positive integer ( x ) that satisfies the condition. If no solution exists, output ( -1 ).

sample

4
1 2 3 4

1