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

给你一个长度为 $n$ 的数组 $a$。对于一个整数 $k$，当且仅当可以通过执行以下操作任意次（可以为零次）将 $a$ 按非降序排列时，称其为“piggy”：

• 首先，选择两个下标 $i$ 和 $j$（满足 $1 \le i \lt j \le n$），使得 $|a_i - a_j| \ge k$；
• 然后，交换 $a_i$ 和 $a_j$。

你需要找出最大的 piggy 整数 $k$。如果不存在这样的整数，则输出 $-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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le 10^9$）—— 数组 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $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.

对于每个测试用例，输出一个整数——最大的“存钱罐整数” $k$。

如果这样的整数不存在，则输出 $-1$。

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.

在第一个和第二个测试用例中，无论 $k$ 的值有多大，都不执行任何操作即可将数组 $a$ 按非降序排列。

在第三个测试用例中，最大的“piggy”整数 $k$ 为 $2$。我们可在第一次操作中选择 $i=2$ 和 $j=3$，因为 $|a_2-a_3|=|4-2|=2 \ge k$，从而使得 $a$ 按非降序排列。可以证明：不存在大于 $2$ 的 piggy 整数。