给定一个数组 $$$a$$$,其中包含 $$$n$$$ 整数和一个整数 $$$k$$$。
如果存在索引序列 $$$i_1, i_2, \dots, i_m$$$ ,则一对 $$$(l,r)$$$ 是好的
- $$$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$$$。
输出
对于每个测试用例,打印良好对的数量。
示例
输入 #1
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
输出 #1
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$$$。