2179C.md (1513B)
1 Source: https://codeforces.com/problemset/problem/2179/C 2 3 C. Blackslex and Number Theory 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 Blackslex worked too hard and started dreaming about numbers. Solve the following task from his dreams. 22 23 You are given an array $a_1, a_2, \ldots, a_n$. 24 25 In one operation you choose an index $i$ ($1 \le i \le n$) and an integer $x$ which is at least $k$ and set $$ a_i := a_i \bmod x, $$ where $u \bmod v$ denotes the remainder of dividing $u$ by $v$. 26 27 Your goal is to make all elements of the array identical. Among all positive integers $k$, determine the maximum $k$ for which there exists a finite sequence of the above operations that makes all array elements equal. 28 29 Input 30 31 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 32 33 The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$). 34 35 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$, all values of $a$ are distinct). 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 38 39 Output 40 41 For each test case, print a single integer — the maximum positive integer $k$ such that it is possible to make all elements of the array identical using any number of operations with moduli $x$ restricted to $k \le x$. 42 43 Example 44 45 Input 46 47 ``` 48 3 49 50 3 51 52 5 7 9 53 54 2 55 56 2 3 57 58 7 59 60 11 74 5 22 52 97 82 61 ``` 62 63 Output 64 65 ``` 66 5 67 68 2 69 70 6 71 ```