题目内容

你有一个长度为 $n$ 的整数序列 $x_1, x_2, \dots, x_n$，每个数的值都在 $1$ 到 $M$ 之间。你可以进行至多一次操作：选择一个位置，将其值修改为 $[1, M]$ 中的任意整数。操作结束后，你将整个序列按升序排列，得到非递减序列 $y_1 \le y_2 \le \dots \le y_n$。定义序列的“最小间隔”为所有相邻两数差值的最小值，即 $\min_{2 \le i \le n} (y_i - y_{i-1})$。你希望通过这至多一次操作，使这个最小间隔尽可能大。请计算能够达到的最大最小间隔。

数据范围：序列的长度 $n$ 满足 $2 \le n \le 2 \times 10^5$，数值上界 $M$ 不超过 $10^9$。序列中的整数均在 $[1, M]$ 内。所有测试数据中 $n$ 的总和不超过 $4 \times 10^5$。

输入描述

第一行包含一个整数 $t$，表示测试数据的组数。接下来依次描述每组数据： 每组数据的第一行包含两个整数 $n$ 和 $M$，分别表示序列的长度和数值上界。 第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$，表示初始序列，每个数均在 $1$ 到 $M$ 之间。

输出描述

对于每组测试数据，输出一行一个整数，表示能够获得的最大最小间隔。

样例1

输入

1
2 10
4 6

输出

6

说明

初始序列排序后为 [4,6]，相邻差为 2。我们可以修改一个数来增大最小间隔。若将 4 修改为 1，得 [1,6]，差值为 5；若将 6 修改为 10，得 [4,10]，差值为 6；若将 6 修改为 1，得 [1,4]，差值为 3。在所有修改中，能得到的最大最小间隔为 6。

样例2

输入

1
3 10
2 4 8

输出

3

说明

排序后为 [2,4,8]，相邻差依次为 2 和 4，当前最小间隔是 2。我们可以删去 4（等价于将其修改后重新插入），剩下 [2,8]，再插入一个新的数 $x$（$1 \le x \le 10$），希望排序后最小间隔尽量大。

当 $x=5$ 时，得到 [2,5,8]，相邻差 3 和 3，最小间隔为 3。尝试其他删除（如删去 2 或 8）并插入，均无法使最小间隔超过 3。因此答案为 3。

样例3

输入

1
4 50
5 20 21 40

输出

10

说明

排序后为 [5,20,21,40]，相邻差为 15、1、19，最小间隔仅为 1。我们可以删去 21，得到 [5,20,40]，内部差 15 和 20 都比较大。在 20 与 40 之间插入 30，形成 [5,20,30,40]，差值依次为 15、10、10，最小间隔提升至 10。

可以验证，无论删去哪一项并重新插入，都无法使最小间隔超过 10，故答案为 10。