解题思路

• 先将原序列排序为 $s_1 \le s_2 \le \cdots \le s_n$，一次形变等价于：从 multiset 中删去某个 $s_k$，再向 $[1,m]$ 中插入一个自由数 $x$，最后排序得到长度为 $n$ 的序列。
• 对固定的目标值 $G$，判定「最小间隔能否 $\ge G$」：若 $G=0$ 恒可行；若 $G>0$，则最终序列中相邻差均 $\ge G$，等价于排序后相邻元素间距至少为 $G$。
• 对固定的 $k$（删去 $s_k$），得到长度 $n-1$ 的有序数组 $t$。在 $t$ 中尚未插入 $x$ 时，$t$ 内部的相邻对若出现间距 $<G$，则必须在最终序列里由 $x$ 插入到该相邻对之间 才能同时把左右两侧都拉开到 $\ge G$；因此 $t$ 中「坏间隔」的个数必须 $\le 1$，否则一次插入无法同时修复。
• 若 $t$ 内坏间隔数为 $0$：只需存在某个插入位置，使 $x$ 与左右邻居（或边界与 $[1,m]$）满足间距 $\ge G$。这等价于：可把 $x$ 放在最左（需 $s_{\text{首}}\ge G+1$ 以容纳 $x=1$）、最右（需 $s_{\text{尾}}\le m-G$ 以容纳 $x=m$），或夹在 $t$ 的某个足够宽的内部缝隙里（需该缝隙长度 $\ge 2G$）。
• 若 $t$ 内恰有 $1$ 个坏间隔 $(u,v)$：必须把 $x$ 放在 $u$ 与 $v$ 之间，且需 $v-u\ge 2G$，并存在整数 $x\in[\max(1,u+G),\min(m,v-G)]$。
• 对所有 $k$ 做一次 $O(n)$ 判定，配合对 $G$ 的二分（上界取 $m$），单组复杂度 $O(n\log m)$；全文件 $\sum n \le 4\times 10^5$ 可过。

题目描述

笨蛋同学有一个长度为 $n$ 的整数序列 $\{a_1,a_2,\ldots,a_n\}$，并且每个数都在 $[1,m]$ 中。
你最多可以做一次“形变”操作（也可以不做）：

• 选择一个下标 $i$，把 $a_i$ 改成区间 $[1,m]$ 内的任意一个整数。

形变结束后，把整个序列从小到大排序，得到 $\{b_1,b_2,\ldots,b_n\}$（满足 $b_1 \le b_2 \le \cdots \le b_n$）。
定义“最小间隔”为：所有相邻两个数的差的最小值，也就是

请你输出：通过最多一次形变操作后，这个“最小间隔”最大可以是多少。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $t(1 \le t \le 2 \times 10^5)$ 代表数据组数，每组测试数据描述如下：

第一行输入两个整数 $n,m(2 \le n \le 2 \times 10^5,\ 1 \le m \le 10^9)$，表示序列的长度与取值上界。
第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n(1 \le a_i \le m)$，表示序列中的每个数。
除此之外，保证单个测试文件的 $n$ 之和不超过 $4 \times 10^5$。

输出描述

对于每一组测试数据，新起一行输出一个整数，表示答案。

示例 1

输入

3
3 10
1 2 8
4 7
1 1 1 7
2 100
30 70

输出

3
0
70