D. Пугало
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На своей апельсиновой плантации мужчина из Флориды получает очередное спам-письмо, доставленное вороной. Естественно, он отправляет его обратно самым неудобным из возможных способов.

Ворона сидит на позиции $$$0$$$ числовой прямой. Есть $$$n$$$ пугал, расположенных на целочисленных координатах $$$a_1, a_2, \ldots, a_n$$$ вдоль числовой прямой. Эти пугала были зачарованы, что позволяет им перемещаться влево и вправо со скоростью $$$1$$$ единица в секунду.

Ворона боится пугал и хочет держаться на расстоянии по крайней мере $$$k$$$ от ближайшего пугала, расположенного на позиции вороны или левее. Для этого ворона использует свою способность к телепортации следующим образом:

  • Пусть $$$x$$$ — текущее положение вороны, а $$$y$$$ — максимальная координата пугала, такая, что $$$y \le x$$$. Если $$$x - y < k$$$, то есть пугало находится слишком близко, то ворона мгновенно телепортируется на позицию $$$y + k$$$.

Эта телепортация происходит мгновенно и непрерывно. Ворона будет продолжать проверять, нет ли пугал, расположенных на её позиции или слева от неё, и телепортироваться всякий раз, когда кто-то подойдет слишком близко (что может произойти в нецелый момент времени). Обратите внимание, что помимо телепортации, ворона не будет передвигаться сама по себе.

Ваша задача состоит в том, чтобы определить минимальное время, необходимое для того, чтобы ворона оказалась на позиции, большей или равной $$$\ell$$$. При этом пугала двигаются оптимально, чтобы позволить вороне достичь своей цели. Для удобства мы просим вывести значение, вдвое больше минимального времени, необходимого вороне для достижения целевой позиции $$$\ell$$$. Можно доказать, что это значение всегда будет целым числом.

Обратите внимание, что пугала могут стартовать, останавливаться или менять направление в любой момент (возможно, в нецелые моменты времени).

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

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

Первая строка каждого набора входных данных содержит три целых числа $$$n, k, \ell$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq k \leq \ell \leq 10^8$$$) — количество пугал, расстояние телепортации и целевое положение вороны, соответственно.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq \ell$$$) — начальные позиции $$$n$$$ пугал.

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

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

Для каждого набора входных данных выведите одно целое число, представляющее удвоенное минимальное время, необходимое вороне для телепортации в положение, большее или равное $$$\ell$$$.

Пример
Входные данные
9
1 3 5
0
3 2 5
2 5 5
1 10 10
10
10 1 10
0 1 2 3 4 5 6 7 8 9
2 1 2
0 0
2 1 2
0 2
2 1 3
0 2
2 2 4
1 1
9 12 54
3 3 8 24 25 27 29 34 53
Выходные данные
4
5
20
0
2
1
2
2
7
Примечание

В первом наборе входных данных ворона мгновенно телепортируется на позицию $$$3$$$ из-за пугала на позиции $$$0$$$. Затем это пугало может переместиться на позицию $$$2$$$, заставляя ворону непрерывно постепенно перемещаться из положения $$$3$$$ в положение $$$5$$$, завершая путешествие за $$$2$$$ секунды. Следовательно, ответ равен $$$4$$$.

Во втором наборе входных данных пугало $$$1$$$ и пугало $$$2$$$ могут переместиться на позиции $$$0$$$ и $$$3$$$ соответственно за $$$2$$$ секунды, в то время как пугало $$$3$$$ остается на позиции $$$5$$$. Ворона телепортируется на позицию $$$2$$$ благодаря пугалу $$$1$$$. Затем пугало $$$1$$$ перемещается вправо, в то время как пугало $$$2$$$ и пугало $$$3$$$ перемещаются влево в течение $$$0.5$$$ секунд. Это приводит к тому, что ворона непрерывно перемещается из положения $$$2$$$ в положение $$$2.5$$$ из-за того, что пугало $$$1$$$ перемещается вправо из положения $$$0$$$. По истечении этой половины секунды пугала окажутся на позициях $$$0.5, 2.5, 4.5$$$. Пугало $$$2$$$, теперь находящееся на позиции $$$2.5$$$, заставляет ворону мгновенно телепортироваться на позицию $$$4.5$$$, а пугало $$$3$$$ на позиции $$$4.5$$$ заставляет её мгновенно телепортироваться на позицию $$$6.5$$$, что превосходит $$$\ell = 5$$$. Таким образом, ворона завершает перемещение за $$$2.5$$$ секунды, а ответ равен $$$5$$$.

Можно показать, что это минимально возможное время для обоих наборов входных данных.