1826B.md (1645B)
1 Source: https://codeforces.com/problemset/problem/1826/B 2 3 B. Lunatic Never Content 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You have an array $a$ of $n$ non-negative integers. Let's define $f(a, x) = [a_1 \bmod x, a_2 \bmod x, \dots, a_n \bmod x]$ for some positive integer $x$. Find the biggest $x$, such that $f(a, x)$ is a palindrome. 22 23 Here, $a \bmod x$ is the remainder of the integer division of $a$ by $x$. 24 25 An array is a palindrome if it reads the same backward as forward. More formally, an array $a$ of length $n$ is a palindrome if for every $i$ ($1 \leq i \leq n$) $a_i = a_{n - i + 1}$. 26 27 Input 28 29 The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. 30 31 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$). 32 33 The second line of each test case contains $n$ integers $a_i$ ($0 \leq a_i \leq 10^9$). 34 35 It's guaranteed that the sum of all $n$ does not exceed $10^5$. 36 37 Output 38 39 For each test case output the biggest $x$, such that $f(a, x)$ is a palindrome. If $x$ can be infinitely large, output $0$ instead. 40 41 Example 42 43 Input 44 45 ``` 46 4 47 48 2 49 50 1 2 51 52 8 53 54 3 0 1 2 0 3 2 1 55 56 1 57 58 0 59 60 3 61 62 100 1 1000000000 63 ``` 64 65 Output 66 67 ``` 68 1 69 2 70 0 71 999999900 72 ``` 73 74 Note 75 76 In the first example, $f(a, x = 1) = [0, 0]$ which is a palindrome. 77 78 In the second example, $f(a, x = 2) = [1, 0, 1, 0, 0, 1, 0, 1]$ which is a palindrome. 79 80 It can be proven that in the first two examples, no larger $x$ satisfies the condition. 81 82 In the third example, $f(a, x) = [0]$ for any $x$, so we can choose it infinitely large, so the answer is $0$.