404638: GYM101597 A Chess

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 {A_i}, and you want to find which M was used.

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

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.

5
1 2 3 4 8

13

2
1 2

3

8
1 1 1 2 2 2 4 4

7

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

49999

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.