You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

你是“元培杯”的出题人，准备了 $n$ 个题目，其中第 $i$ 个题目的难度为 $a_i$。你将进行以下操作：

• 从列表中删除一些(可能为零)题目；
• 以任意顺序重新排列剩下的题目。

只有当任意两个连续题目的难度之差的绝对值最多为$k$(小于等于$k$)时，题目才被认为是难度均衡的。

你需要删除最少数量的问题，以使题目的难度排列是均衡的。

C++中sort排序函数：sort (first, last)

用法：对容器或普通数组中 [first, last) 范围内的元素进行排序，默认进行升序排序。

例如对数组的前10个元素进行排序：

int a[10] = {2, 4, 1, 23, 5, 76, 0, 43, 24, 65};
for(int i = 0; i < 10; i++)
    cout << a[i] << " ";
cout << endl;
sort(a, a + 10);
for(int i = 0; i < 10; i++)
    cout << a[i] << " ";

输入格式

第一行包含一个正整数$t$。表示接下来有$t$个测试用例。

每个测试用例的第一行包含两个正整数 $n$和 $k$，表示题目的数量以及连续题目之间允许的最大差值的绝对值。

每个测试用例的第二行包含$n$个以空格分隔的整数$a_i$，表示每个问题的难度。

输出格式

对于每个测试用例，输出一个整数，即需要删除的最少题目数量，使得题目的排列是均衡的。

7
5 1
1 2 4 5 6
1 2
10
8 3
17 3 1 20 12 5 17 12
4 2
2 4 6 8
5 3
2 3 19 10 8
3 4
1 10 5
8 1
8 3 1 4 5 10 7 3

2
0
5
0
3
1
4

提示

【样例解释】

对于第一个测试用例，我们可以删除前两个问题，并使用难度为 $[4,5,6]$ 的问题构建一个集合，其中相邻问题的难度之差等于 $|5-4|=1\leq1$和$|6-5|=1\leq1$。

对于第二个测试用例，我们可以只取一个问题，并使用难度为 $10$ 的问题组成一个回合。

依此类推，每个测试用例都可以按照相同的方式解决。

【数据范围】

对于$10\%$的数据，保证$t\leq1000,n\leq 10,1\leq k \leq 10^9$。

对于$20\%$的数据，保证$t\leq1000,n\leq 10^2,1\leq k \leq 10^9$。

对于$30\%$的数据，保证$t\leq100,n\leq 10^3,1\leq k \leq 10^9$。

对于$100\%$的数据，保证$t\leq1000,n\leq 2\cdot10^5,1\leq k \leq 10^9$，同时保证每一个测试点中 $n$的总和不超过 $2\cdot10^5$。