CF2179C Blackslex and Number Theory

Blackslex worked too hard and started dreaming about numbers. Solve the following task from his dreams. You are given an array $ a_1, a_2, \ldots, a_n $ . 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 $ . 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.

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ). 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). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

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 $ .