CF2187A Restricted Sorting

给定一个长度为 $n$ 的数组 $a$。对于一个整数 $k$，如果可以通过任意多次（也可以不进行）以下操作将 $a$ 排序为非降序，则称该整数是「piggy」的： - 首先，选择两个下标 $i$ 和 $j$（$1 \le i < j \le n$），使得 $|a_i - a_j| \ge k$； - 然后交换 $a_i$ 和 $a_j$。 你需要确定最大的「piggy」整数 $k$。如果不存在这样的整数，输出 $-1$。

每组输入包含若干组测试数据。第一行为测试组数 $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 \cdot 10^5$。

对于每组测试数据，输出一个整数，表示最大的「piggy」整数 $k$。 如果不存在这样的整数，输出 $-1$。

在第一和第二组测试数据中，无论 $k$ 多大，都可以选择不进行任何操作，即可将 $a$ 排序为非降序。 在第三组测试数据中，最大的「piggy」整数 $k$ 为 $2$。我们可以在第一次操作时选择 $i=2$ 和 $j=3$，因为 $|a_2-a_3|=|4-2|=2 \ge k$，此时 $a$ 即可按非降序排列。可以证明不存在更大的「piggy」整数。 由 ChatGPT 5 翻译