CF2187A Restricted Sorting

You are given an array $ a $ of length $ n $ . For an integer $ k $ , we call it piggy if and only if it is possible to sort $ a $ in non-descending order by performing the following operation an arbitrary number of times (possibly zero): - First, select two indices $ i $ and $ j $ ( $ 1 \le i < j \le n $ ) such that $ |a_i - a_j| \ge k $ ; - Then, swap $ a_i $ and $ a_j $ . You need to determine the largest piggy integer $ k $ . If such an integer does not exist, output $ -1 $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of $ a $ . The second line contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the elements of $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot10^5 $ .

For each test case, output a single integer — the largest piggy integer $ k $ . If such an integer does not exist, output $ -1 $ instead.

In the first and the second test case, no matter how large $ k $ is, you can always sort $ a $ in non-descending order by not performing any operations. In the third test case, the largest piggy $ k $ is $ 2 $ . We can select $ i=2 $ and $ j=3 $ in the first operation, since $ |a_2-a_3|=|4-2|=2 \ge k $ , and $ a $ is sorted in non-descending order. It can be proven that no piggy integers larger than $ 2 $ exist.