{"raw_statement":[{"iden":"statement","content":"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.\n\nPaul 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. \n\nYou have recovered a sorted sequence of these numbers {Ai}, and you want to find which M was used. \n\nFirst 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.\n\nOutput 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.\n\nIn the first test case, the numbers written on squares, in order, are 1, 2, 4, 8 and 3 (2·8 mod 13). \n\nIn the second test case, the smallest possible solution is 3, but other numbers, like 7 or 11, would also work.\n\nIn the third case, note that the numbers can repeat and it is possible for N to be larger than M.\n\nFourth case sees a well-known prime in action. \n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input51 2 3 4 8Output13Input21 2Output3Input81 1 1 2 2 2 4 4Output7Input241 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 12149 15537 16384 24298 31074 32768 38775 44387 47193 48596Output49999"},{"iden":"note","content":"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. "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of squares.  \nLet $ A = (A_1, A_2, \\dots, A_N) $ be a sorted sequence of integers such that $ A_i \\equiv 2^{i-1} \\pmod{M} $ for some modulus $ M \\in \\mathbb{Z}^+ $, and $ 0 \\le A_i < M $.  \n\n**Constraints**  \n1. $ 1 \\le N \\le 2 \\cdot 10^5 $  \n2. $ 0 \\le A_i \\le 10^{18} $ for all $ i \\in \\{1, \\dots, N\\} $  \n3. The sequence $ A $ is non-decreasing: $ A_1 \\le A_2 \\le \\dots \\le A_N $  \n4. There exists at least one $ M $ satisfying the condition.  \n\n**Objective**  \nFind the smallest positive integer $ M $ such that:  \n$$\n\\forall i \\in \\{1, \\dots, N\\}, \\quad A_i \\equiv 2^{i-1} \\pmod{M}\n$$  \nand $ A_i < M $ for all $ i $.","simple_statement":"Given a sorted sequence of N numbers representing powers of 2 modulo M (starting from 2^0, 2^1, 2^2, ...), find the smallest possible M that could have produced this sequence.","has_page_source":false}