CF1762F.Good Pairs

You are given an array $a$ consisting of $n$ integers and an integer $k$.

A pair $(l,r)$ is good if there exists a sequence of indices $i_1, i_2, \dots, i_m$ such that

• $i_1=l$ and $i_m=r$;
• $i_j \lt i_{j+1}$ for all $1 \leq j \lt m$; and
• $|a_{i_j}-a_{i_{j+1}}| \leq k$ for all $1 \leq j \lt m$.

Find the number of pairs $(l,r)$ ($1 \leq l \leq r \leq n$) that are good.

给你一个包含 $n$ 个整数的数组 $a$ 和一个整数 $k$。

若存在一个下标序列 $i_1, i_2, \dots, i_m$，使得

• $i_1=l$ 且 $i_m=r$；
• 对所有 $1 \leq j \lt m$，有 $i_j \lt i_{j+1}$；且
• 对所有 $1 \leq j \lt m$，有 $|a_{i_j}-a_{i_{j+1}}| \leq k$，

则称二元组 $(l,r)$ 是“好的”。

求满足 $1 \leq l \leq r \leq n$ 的“好”的二元组 $(l,r)$ 的个数。

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two space-separated integers $n$ and $k$ ($1 \leq n \leq 5 \cdot 10^5$; $0 \leq k \leq 10^5$) — the length of the array $a$ and the integer $k$.

The second line of each test case contains $n$ space-separated integers $a_1,a_2,\ldots,a_n$ ($1 \leq a_i \leq 10^5$) — representing the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case, print the number of good pairs.

对于每个测试用例，输出好对的数量。

In the first test case, good pairs are $(1,1)$, $(1,2)$, $(1,3)$, $(2,2)$, $(2,3)$, and $(3,3)$.

In the second test case, good pairs are $(1,1)$, $(1,3)$, $(1,4)$, $(2,2)$, $(2,3)$, $(2,4)$, $(3,3)$, $(3,4)$ and $(4,4)$. Pair $(1,4)$ is good because there exists a sequence of indices $1, 3, 4$ which satisfy the given conditions.

在第一个测试用例中，好的数对为 $(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$ 满足题目所给的条件。