Rescheduling the Exam
Contest: Codeforces Round 776 (Div. 3)
Difficulty rating: 1900
Tags: binary search, data structures, greedy, implementation, math, sortings

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).

Input format:
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 < 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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
9
3 12
3 5 9
2 5
1 5
2 100
1 2
5 15
3 6 9 12 15
3 1000000000
1 400000000 500000000
2 10
3 4
2 2
1 2
4 15
6 11 12 13
2 20
17 20

Example output:
2
1
1
2
99999999
3
0
1
9

Editorial:
To begin with, we will learn how to find the optimal place for the exam that we want to move. Let's imagine that it is not in the schedule, in this case we have two options:
• Put the exam at the end of the session so that there are $$$d - a_n - 1$$$ days before it.
• Put it in the middle of the largest break between exams ((let its length be $$$mx$$$), so that between it and the nearest one there is $$$\left\lfloor \frac{mx - 1}{2} \right\rfloor$$$, because this is no worse than putting it in any part of any other break.
That is, the answer for such an arrangement is  — the minimum of the larger of these options and the minimum break, in schedule without the moved exam.
Now note that the minimum break in most variants is the same — minimum in the initial schedule. So in order to reduce $$$\mu$$$, you need to move exactly one of the two exams that form it and you need to check which of the two options is better.