2187A.md (1805B)
1 Source: https://codeforces.com/problemset/problem/2187/A 2 3 A. Restricted Sorting 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 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): 22 23 * First, select two indices $i$ and $j$ ($1 \le i \lt j \le n$) such that $|a_i - a_j| \ge k$; 24 * Then, swap $a_i$ and $a_j$. 25 26 You need to determine the largest piggy integer $k$. If such an integer does not exist, output $-1$. 27 28 Input 29 30 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. 31 32 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of $a$. 33 34 The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$) — the elements of $a$. 35 36 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$. 37 38 Output 39 40 For each test case, output a single integer — the largest piggy integer $k$. 41 42 If such an integer does not exist, output $-1$ instead. 43 44 Example 45 46 Input 47 48 ``` 49 5 50 51 1 52 53 1 54 55 5 56 57 1 2 3 4 5 58 59 3 60 61 1 4 2 62 63 5 64 65 2 1 5 4 3 66 67 6 68 69 1 1 4 5 1 4 70 ``` 71 72 Output 73 74 ``` 75 -1 76 77 -1 78 79 2 80 81 2 82 83 3 84 ``` 85 86 Note 87 88 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. 89 90 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.