C. 迁徙 / migrate
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

海上有 $$$n$$$ 座岛屿，自北向南排成一条直线，其中第 $$$i$$$（$$$1 \le i \le n$$$）座岛屿在这条直线上的坐标为整数 $$$x_i$$$，且 $$$x_1 \lt x_2 \lt \cdots \lt x_n$$$。每年秋季，一群海鸟会沿着这条直线在南北方向上迁徙，小 P 正在观察它们。

海鸟的体力有限，每次飞行的距离都不超过 $$$d$$$。若两座岛屿 $$$i,j$$$（$$$1 \le i,j \le n$$$）满足 $$$|x_i-x_j| \le d$$$，海鸟就可以从第 $$$i$$$ 座岛屿直接飞到第 $$$j$$$ 座岛屿。

对于两座不同的岛屿 $$$u,v$$$（$$$1 \le u,v \le n$$$），一条从第 $$$u$$$ 座岛屿到第 $$$v$$$ 座岛屿的路径形如 $$$y_1 \to y_2 \to \cdots \to y_m$$$，其中 $$$y_1=u$$$，$$$y_m=v$$$，且对于所有 $$$l$$$（$$$1 \le l \le m-1$$$），海鸟都能够从第 $$$y_l$$$ 座岛屿直接飞到第 $$$y_{l+1}$$$ 座岛屿；其长度为 $$$m-1$$$，即海鸟在路径中飞行的次数。

小 P 发现，海鸟在迁徙时总是会选择长度最短的路径。对于两座岛屿 $$$u,v$$$（$$$1 \le u \lt v \le n$$$），若从第 $$$u$$$ 座岛屿到第 $$$v$$$ 座岛屿的长度最短的路径恰好有两条，海鸟可以分成两群，分别沿其中一条飞往第 $$$v$$$ 座岛屿；此时称 $$$(u,v)$$$ 为双径岛屿对。两条路径不同，当且仅当它们经过的岛屿序列不完全相同。

你需要帮助小 P 求出双径岛屿对的数量。

Input

从标准输入读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数 $$$c,t$$$，分别表示测试点编号与测试数据组数。特别地，若 $$$c=0$$$，则该测试点为样例。

接下来依次输入 $$$t$$$ 组测试数据。对于每组测试数据：

  • 第一行包含两个正整数 $$$n,d$$$，分别表示岛屿数量和海鸟一次最多能飞行的距离。
  • 第二行包含 $$$n$$$ 个严格递增的整数 $$$x_1,x_2,\ldots,x_n$$$，依次表示每座岛屿的坐标。
Output

输出到标准输出。

对于每组测试数据，输出一行一个非负整数，表示双径岛屿对的数量。

Examples
Input
0 2
4 2
1 2 3 4
5 2
1 2 3 4 5
Output
1
2
Input
0 2
5 3
-2 -1 0 1 2
6 2
-4 -3 -2 -1 3 6
Output
0
1
Note

补充样例文件可从原题页面的附件下载：https://www.luogu.com.cn/problem/P17833。

样例 1 解释

该样例共包含两组测试数据。

对于第一组测试数据，仅有 $$$1$$$ 个双径岛屿对 $$$(1,4)$$$。从第 $$$1$$$ 座岛屿到第 $$$4$$$ 座岛屿有两条长度最短的路径，分别为 $$$1 \to 2 \to 4$$$ 和 $$$1 \to 3 \to 4$$$。

对于第二组测试数据，共有 $$$2$$$ 个双径岛屿对，分别为 $$$(1,4)$$$ 和 $$$(2,5)$$$。从第 $$$1$$$ 座岛屿到第 $$$5$$$ 座岛屿只有一条长度最短的路径 $$$1 \to 3 \to 5$$$，因此 $$$(1,5)$$$ 不是双径岛屿对。

样例 2 解释

该样例共包含两组测试数据。

对于第一组测试数据，共有 $$$0$$$ 个双径岛屿对。从第 $$$1$$$ 座岛屿到第 $$$5$$$ 座岛屿有三条长度最短的路径，分别为 $$$1 \to 2 \to 5$$$，$$$1 \to 3 \to 5$$$ 和 $$$1 \to 4 \to 5$$$，因此 $$$(1,5)$$$ 不是双径岛屿对。

对于第二组测试数据，仅有 $$$1$$$ 个双径岛屿对 $$$(1,4)$$$。从第 $$$1$$$ 座岛屿到第 $$$4$$$ 座岛屿有两条长度最短的路径，分别为 $$$1 \to 2 \to 4$$$ 和 $$$1 \to 3 \to 4$$$。第 $$$5$$$ 座和第 $$$6$$$ 座岛屿均无法到达任何其他岛屿。

样例 3

见题目目录下的 migrate/3.in 与 migrate/3.ans。

该样例满足测试点 $$$3 \sim 6$$$ 的约束条件。

样例 4

见题目目录下的 migrate/4.in 与 migrate/4.ans。

该样例满足测试点 $$$11,12$$$ 的约束条件。

样例 5

见题目目录下的 migrate/5.in 与 migrate/5.ans。

该样例满足测试点 $$$15 \sim 18$$$ 的约束条件。

样例 6

见题目目录下的 migrate/6.in 与 migrate/6.ans。

该样例满足测试点 $$$19 \sim 21$$$ 的约束条件。

数据范围

设 $$$N$$$ 为单个测试点内所有测试数据的 $$$n$$$ 的和。对于所有测试数据，均有：

  • $$$0 \le c \le 25$$$，$$$2 \le t \le 10^5$$$；
  • $$$1 \le n \le 2 \times 10^6$$$，$$$N \le 2 \times 10^6$$$，$$$1 \le d \le 2 \times 10^{18}$$$；
  • $$$-10^{18} \le x_1 \lt x_2 \lt \cdots \lt x_n \le 10^{18}$$$。
测试点编号$$$N \le$$$特殊性质
$$$1,2$$$$$$9$$$无
$$$3 \sim 6$$$$$$300$$$无
$$$7 \sim 10$$$$$$5000$$$无
$$$11,12$$$$$$2 \times 10^6$$$A
$$$13,14$$$$$$2 \times 10^6$$$B
$$$15 \sim 18$$$$$$10^6$$$C
$$$19 \sim 21$$$$$$2 \times 10^5$$$无
$$$22 \sim 25$$$$$$2 \times 10^6$$$无

特殊性质 A：$$$x_1,x_2,\ldots,x_n$$$ 构成等差数列。

特殊性质 B：存在一座岛屿，使得海鸟可以从该岛屿直接飞到任意其他岛屿。

特殊性质 C：$$$x_n-x_1 \le 10d$$$。

本题满分 100 分。官方测试点共 25 个，每个测试点 4 分，独立计分。展示样例中，与官方测试点完全相同的样例保留原测试点分值；其余样例不计分。