C. Ещё одна задача про чёрные клетки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вдохновлено этой задачей.

Есть полоска, разделённая на клетки, пронумерованные слева направо от $$$0$$$ до $$$10^9$$$. Изначально все клетки белые.

Дан массив $$$a$$$ длины $$$n$$$, содержащий индексы $$$n$$$ клеток. Мы хотим покрасить все эти $$$n$$$ клеток в чёрный цвет.

Для данного целого числа $$$x$$$ можно выбрать целое число $$$y$$$ такое, что $$$0 \le y \le x$$$, а затем произвольно выбрать $$$y$$$ клеток, которые не входят в $$$a$$$. Эти выбранные $$$y$$$ клеток также требуется покрасить в чёрный цвет, оставив все остальные клетки белыми.

Вы можете выполнить следующую операцию любое количество раз:

  • Выбрать две различные клетки $$$i$$$ и $$$j$$$ такие, что $$$1 \le |i-j| \le k$$$, и покрасить их в чёрный цвет независимо от того, были ли они до этого чёрными или белыми.

Найдите минимальное значение $$$k$$$, при котором можно покрасить все требуемые клетки в чёрный цвет, оставив остальные клетки белыми.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$x$$$ ($$$2\leq n\leq 2\cdot 10^5,0\leq x\leq n$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$0\leq a_i\leq 10^{9}$$$). Гарантируется, что $$$a_i \lt a_{i+1}$$$ для всех $$$1 \leq i \lt n$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное значение $$$k$$$, при котором можно покрасить все требуемые клетки в чёрный цвет, оставив остальные клетки белыми.

Пример
Входные данные
4
2 0
1 3
2 1
1 3
3 1
2 5 7
10 2
0 6 8 10 13 14 16 19 25 31
Выходные данные
2
1
2
3
Примечание

В первом примере нельзя покрасить в чёрный никакие клетки, кроме $$$1$$$ и $$$3$$$, поскольку $$$x=0$$$. Поэтому оптимально положить $$$k=2$$$ и выбрать $$$i=1,j=3$$$ в первой операции.

Во втором примере можно положить $$$k=1$$$, что является минимально возможным значением. Сначала выберем для покраски $$$i=1,j=2$$$, а затем — $$$i=2,j=3$$$. После этого клетки $$$1,2,3$$$ покрашены в чёрный цвет, и только клетка $$$2$$$ отсутствует в данном списке, что удовлетворяет условию $$$x=1$$$.