404638: GYM101597 A Chess

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Chesstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

A legend says that, as a reward for inventing chess, the creator asked his ruler for 1 grain of rice on the first square, 2 on the second, 4 on the third, and on each of the following twice the amount of the preceding square. The ruler at first laughed it off as a meager prize for such a remarkable invention, but soon (around the 3rd rank, where he needed more than millions of grains) realized his mistake.

Paul invented a new version of chess, that uses N squares and assigned each square a value the same way. However, for convenience, he used all the numbers modulo some positive integer M.

You have recovered a sorted sequence of these numbers {Ai}, and you want to find which M was used.

Input

First line contains a single number 1 ≤ N ≤ 2·105, the number of squares on the chessboard. The next line contains N sorted numbers 0 ≤ Ai ≤ 1018, representing the values written on squares. It is guaranteed that a solution exists.

Output

Output a single line with a single integer M, the modulus that was used for the original calculation. If there are multiple solutions, print the smallest one.

ExamplesInput
5
1 2 3 4 8
Output
13
Input
2
1 2
Output
3
Input
8
1 1 1 2 2 2 4 4
Output
7
Input
24
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 12149 15537 16384 24298 31074 32768 38775 44387 47193 48596
Output
49999
Note

In the first test case, the numbers written on squares, in order, are 1, 2, 4, 8 and 3 (2·8 mod 13).

In the second test case, the smallest possible solution is 3, but other numbers, like 7 or 11, would also work.

In the third case, note that the numbers can repeat and it is possible for N to be larger than M.

Fourth case sees a well-known prime in action.

加入题单

上一题 下一题 算法标签: