CF1650E Rescheduling the Exam

现在 Dmitry 正在参加考试周，他需要通过 $n$ 门考试。考试周从第 $1$ 天开始，持续 $d$ 天。第 $i$ 门考试将在第 $a_i$ 天进行（$1 \le a_i \le d$），所有 $a_i$ 互不相同。  如图所示，$n=3$，$d=12$，$a=[3,5,9]$。橙色为考试日。在第一次考试前 Dmitry 休息了 $2$ 天，第二次考试前休息了 $1$ 天，第三次考试前休息了 $3$ 天。对于考试周的安排，Dmitry 关注一个特殊的值 $\mu$——即所有考试前休息天数中的最小值。例如，上图中 $\mu=1$。换句话说，他会统计恰好 $n$ 个数——即第 $i-1$ 次考试和第 $i$ 次考试之间（对于 $i=0$，是从考试周开始到第 $i$ 次考试）他休息了多少天。然后取这 $n$ 个数中的最小值作为 $\mu$。 Dmitry 认为他可以优化考试周的安排。他可以请求将某一门考试的日期更改为任意一天（即可以任意更改一个 $a_i$ 的值）。请帮助他更改考试日期，使得所有 $a_i$ 仍然互不相同，并且 $\mu$ 的值尽可能大。 例如，对于上面的安排，Dmitry 最优的做法是将第二门考试移到考试周的最后一天。新的安排如下：  此时各次考试前的休息天数为 $[2,2,5]$，因此 $\mu=2$。如果没有办法通过移动一场考试来提升 $\mu$，Dmitry 也可以选择不更改原有安排。

输入的第一行为整数 $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 < a_{i+1}$），第 $i$ 个数表示第 $i$ 门考试的日期。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示在可以将任意一场考试移动到任意一天（所有 $a_i$ 仍然互不相同）的情况下，$\mu$ 的最大可能值。

第一个样例已在题面中解析。 第二个样例的最优调整方式之一：  初始安排。  新的安排。 第三个样例中，需要将第 $1$ 天的考试移动到第 $4$ 天到第 $100$ 天中的任意一天。 第四个样例中，任何调整都会使 $\mu$ 变小，因此应保持原安排不变。 第五个样例中，需要将第 $1$ 天的考试移动到第 $100000000$ 天到第 $300000000$ 天中的任意一天。 第六个样例的最优调整方式之一：  初始安排。  新的安排。 第七个样例中，每一天都是考试日，无法重新安排。 由 ChatGPT 4.1 翻译