F. Тройная атака
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Зевс анализирует запись боя, чтобы понять схемы атаки своего противника. У противника есть особая способность: если он нанесет три удара по цели в течение временного интервала $$$z$$$, его третий удар становится мощным, усиленным ударом.

Чтобы переиграть своего противника, Зевс не должен позволить ему активировать свой усиленный удар. Пусть $$$Y = \{y_1, y_2, \ldots, y_m\}$$$ — это мультисет из $$$m$$$ временных меток, где каждый $$$y_i$$$ представляет время, когда удар противника попал в цель. Мы называем $$$Y$$$ безопасным, если для каждой тройки временных меток $$$\{y_i, y_j, y_k\}$$$, таких что $$$1 \le i \lt j \lt k \le m$$$, выполняется условие $$$\max(y_i, y_j, y_k) - \min(y_i, y_j, y_k) \gt z$$$, где $$$z$$$ — это заданная продолжительность временного интервала.

У Зевса есть журнал из $$$n$$$ временных меток $$$x_1, x_2, \ldots, x_n$$$, представляющих время, когда удары противника попали в цель. Временные метки отсортированы в неубывающем порядке появления. Другими словами, $$$x_i \le x_{i+1}$$$ для всех $$$1 \le i \lt n$$$.

У Зевса есть $$$q$$$ интервалов интереса, обозначенных двумя целыми числами $$$1 \le l \le r \le n$$$. Для каждого интервала Зевс хочет найти максимальное количество ударов среди $$$[x_l, x_{l+1}, \ldots, x_r]$$$, которые он мог бы пропустить: другими словами, Зевс хочет найти максимальное по размеру подмножество мультисета $$$\{x_l, x_{l+1}, \ldots, x_r\}$$$, такое что это подмножество безопасно.

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

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

Первая строка содержит два целых числа $$$n$$$ и $$$z$$$ ($$$1 \le n \le 250\,000$$$, $$$1 \le z \le 10^9$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \le x_i \le 10^9$$$) — временные метки ударов. Гарантируется, что массив $$$x$$$ отсортирован, т.е. $$$x_i \le x_{i+1}$$$ для всех $$$1 \le i \lt n$$$.

Третья строка содержит одно целое число $$$q$$$ ($$$1 \le q \le 250\,000$$$).

Следующие $$$q$$$ строк содержат по два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) — концы интервала.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$250\,000$$$.

Гарантируется, что сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$250\,000$$$.

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

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

Пример
Входные данные
3
6 10
1 5 7 8 11 12
6
1 6
1 5
2 6
1 4
2 5
3 6
6 1
1 1 1 3 3 3
2
3 3
1 6
12 15
4 5 15 24 27 32 36 39 40 46 48 48
20
1 12
1 11
6 10
1 8
8 12
11 12
2 9
3 8
7 8
7 10
4 8
9 12
9 10
2 12
1 5
3 12
4 8
3 7
7 12
10 11
Выходные данные
3
2
2
2
2
2
1
4
6
6
2
4
2
2
5
3
2
2
2
2
2
6
4
5
2
3
2
2
Примечание

В первом запросе первого примера мы рассматриваем временные метки $$$\{1, 5, 7, 8, 11, 12\}$$$ с $$$z=10$$$. Подмножество $$$\{1, 5, 12\}$$$ безопасно, потому что его единственная тройка удовлетворяет условию $$$12 - 1 = 11 \gt 10$$$. Невозможно сформировать безопасное подмножество размером $$$4$$$, следовательно, ответ на этот запрос равен $$$3$$$.

В первом запросе второго набора входных данных мы рассматриваем временные метки $$$\{1\}$$$ с $$$z=1$$$. Весь набор $$$\{1\}$$$ является безопасным, поскольку в нём нет троек. Следовательно, ответ на этот запрос — $$$1$$$.

Во втором запросе второго набора входных данных мы рассматриваем временные метки $$$\{1,1,1,3,3,3\}$$$ с $$$z=1$$$.

Подмножество $$$S = \{1,1,3,3\}$$$ является безопасным, потому что:

  • Для тройки $$$(i,j,k) = (1,2,3)$$$, $$$\max(1,1,3) - \min(1,1,3) = 2 \gt 1$$$.
  • Для тройки $$$(i,j,k) = (1,2,4)$$$, $$$\max(1,1,3) - \min(1,1,3) = 2 \gt 1$$$.
  • Для тройки $$$(i,j,k) = (1,3,4)$$$, $$$\max(1,3,3) - \min(1,3,3) = 2 \gt 1$$$.
  • Для тройки $$$(i,j,k) = (2,3,4)$$$, $$$\max(1,3,3) - \min(1,3,3) = 2 \gt 1$$$.

Невозможно сформировать безопасное подмножество размером $$$5$$$, поэтому ответ на этот запрос — $$$4$$$.