A16480 | $Restricted Sorting$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一个长度为 $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$。

输入 #1

5
1
1
5
1 2 3 4 5
3
1 4 2
5
2 1 5 4 3
6
1 1 4 5 1 4

输出 #1

C++ 编辑器

输入

输出