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

Вам дан массив $$$a$$$ из $$$n$$$ целых чисел, а также целое число $$$k$$$.

Пара индексов $$$(l,r)$$$ называется хорошей, если существует последовательность индексов $$$i_1, i_2, \dots, i_m$$$ такая, что

  • $$$i_1=l$$$ и $$$i_m=r$$$;
  • $$$i_j < i_{j+1}$$$ для всех $$$1 \leq j < m$$$; а также
  • $$$|a_{i_j}-a_{i_{j+1}}| \leq k$$$ для всех $$$1 \leq j < m$$$.

Найдите количество хороших пар $$$(l,r)$$$ ($$$1 \leq l \leq r \leq n$$$).

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

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq 10^5$$$) — массив $$$a$$$.

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

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

Для каждого набора входных данных выведите число хороших пар.

Пример
Входные данные
4
3 0
1 1 1
4 2
4 8 6 8
6 4
7 2 5 8 3 8
20 23
110 57 98 14 20 1 60 82 108 37 82 73 8 46 38 35 106 115 58 112
Выходные данные
6
9
18
92
Примечание

В первом примере хорошие пары равны $$$(1,1)$$$, $$$(1,2)$$$, $$$(1,3)$$$, $$$(2,2)$$$, $$$(2,3)$$$ и $$$(3,3)$$$.

Во втором примере хорошие пары равны $$$(1,1)$$$, $$$(1,3)$$$, $$$(1,4)$$$, $$$(2,2)$$$, $$$(2,3)$$$, $$$(2,4)$$$, $$$(3,3)$$$, $$$(3,4)$$$ и $$$(4,4)$$$. Пара $$$(1,4)$$$ является хорошей, так как существует последовательность индексов $$$1, 3, 4$$$, удовлетворяющая всем ограничениям.