CF1650E.Rescheduling the Exam

Now Dmitry has a session, and he has to pass $n$ exams. The session starts on day $1$ and lasts $d$ days. The $i$th exam will take place on the day of $a_i$ ($1 \le a_i \le d$), all $a_i$ — are different.

Sample, where $n=3$, $d=12$, $a=[3,5,9]$. Orange — exam days. Before the first exam Dmitry will rest $2$ days, before the second he will rest $1$ day and before the third he will rest $3$ days.

For the session schedule, Dmitry considers a special value $\mu$ — the smallest of the rest times before the exam for all exams. For example, for the image above, $\mu=1$. In other words, for the schedule, he counts exactly $n$ numbers — how many days he rests between the exam $i-1$ and $i$ (for $i=0$ between the start of the session and the exam $i$). Then it finds $\mu$ — the minimum among these $n$ numbers.

Dmitry believes that he can improve the schedule of the session. He may ask to change the date of one exam (change one arbitrary value of $a_i$). Help him change the date so that all $a_i$ remain different, and the value of $\mu$ is as large as possible.

For example, for the schedule above, it is most advantageous for Dmitry to move the second exam to the very end of the session. The new schedule will take the form:

Now the rest periods before exams are equal to $[2,2,5]$. So, $\mu=2$.

Dmitry can leave the proposed schedule unchanged (if there is no way to move one exam so that it will lead to an improvement in the situation).

现在德米特里有一场考试季，他需要通过 $n$ 门考试。考试季从第 $1$ 天开始，持续 $d$ 天。第 $i$ 门考试将在第 $a_i$ 天举行（$1 \le a_i \le d$），所有 $a_i$ 互不相同。

示例：$n=3$，$d=12$，$a=[3,5,9]$。橙色表示考试日。在第一门考试前，德米特里休息 $2$ 天；在第二门考试前，他休息 $1$ 天；在第三门考试前，他休息 $3$ 天。

对于该考试安排，德米特里定义了一个特殊值 $\mu$ —— 所有考试前的休息天数中的最小值。例如，对上图所示安排，$\mu = 1$。换言之，对于该安排，他精确计算出 $n$ 个数值：即第 $i-1$ 门考试与第 $i$ 门考试之间的休息天数（当 $i = 0$ 时，指考试季开始（第 $1$ 天）到第 $i$ 门考试之间的天数）。然后，$\mu$ 就是这 $n$ 个数中的最小值。

德米特里认为自己可以优化考试安排。他可以申请将其中一门考试的日期进行调整（即任意修改一个 $a_i$ 的值）。请你帮他选择一个考试并更改其日期，使得所有 $a_i$ 仍互不相同，且 $\mu$ 的值尽可能大。

例如，对上述安排，对德米特里最有利的做法是将第二门考试移到考试季的最后一天。新的安排如下：

此时各门考试前的休息天数为 $[2,2,5]$，因此 $\mu = 2$。

德米特里也可以保持原安排不变（即若不存在任何一次单门考试日期的调整能带来 $\mu$ 的提升）。

The first line of input data contains an integer $t$ ($1 \le t \le 10^4$) — the number of input test cases. The descriptions of test cases follow.

An empty line is written in the test before each case.

The first line of each test case contains two integers $n$ and $d$ ($2 \le n \le 2 \cdot 10^5, 1 \le d \le 10^9$) — the number of exams and the length of the session, respectively.

The second line of each test case contains $n$ integers $a_i$ ($1 \le a_i \le d, a_i \lt a_{i+1}$), where the $i$-th number means the date of the $i$-th exam.

It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$.

输入数据的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示输入测试用例的数量。随后是各测试用例的描述。

每个测试用例前均有一空行。

每个测试用例的第一行包含两个整数 $n$ 和 $d$（$2 \le n \le 2 \cdot 10^5,\ 1 \le d \le 10^9$），分别表示考试科目的数量和整个考试期的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le d,\ a_i \lt a_{i+1}$），其中第 $i$ 个数表示第 $i$ 次考试的日期。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, output the maximum possible value of $\mu$ if Dmitry can move any one exam to an arbitrary day. All values of $a_i$ should remain distinct.

对于每个测试用例，输出在德米特里可以将任意一场考试移动到任意一天的前提下，$\mu$ 的最大可能值。所有 $a_i$ 的值必须保持互不相同。

The first sample is parsed in statement.

One of the optimal schedule changes for the second sample:

Initial schedule.

New schedule.

In the third sample, we need to move the exam from day $1$ to any day from $4$ to $100$.

In the fourth sample, any change in the schedule will only reduce $\mu$, so the schedule should be left as it is.

In the fifth sample, we need to move the exam from day $1$ to any day from $100000000$ to $300000000$.

One of the optimal schedule changes for the sixth sample:

Initial schedule.

New schedule.

In the seventh sample, every day is exam day, and it is impossible to rearrange the schedule.

第一个样例在题目描述中已解析。

第二个样例的一种最优调度调整方案：

初始调度。

新调度。

在第三个样例中，我们需要将考试从第 $1$ 天移到第 $4$ 天至第 $100$ 天之间的任意一天。

在第四个样例中，对调度的任何更改都只会使 $\mu$ 减小，因此调度应保持不变。

在第五个样例中，我们需要将考试从第 $1$ 天移到第 $100000000$ 天至第 $300000000$ 天之间的任意一天。

第六个样例的一种最优调度调整方案：

初始调度。

新调度。

在第七个样例中，每一天都是考试日，因此无法重新安排调度。