CF1850D.Balanced Round

You are the author of a Codeforces round and have prepared $n$ problems you are going to set, problem $i$ having difficulty $a_i$. You will do the following process:

• remove some (possibly zero) problems from the list;
• rearrange the remaining problems in any order you wish.

A round is considered balanced if and only if the absolute difference between the difficulty of any two consecutive problems is at most $k$ (less or equal than $k$).

What is the minimum number of problems you have to remove so that an arrangement of problems is balanced?

你是一场 Codeforces 比赛的出题人，已准备了 $n$ 道题目，其中第 $i$ 道题的难度为 $a_i$。你将执行如下操作：

• 从题目列表中移除若干道题（可能一道也不移除）；
• 将剩余题目以任意顺序重新排列。

当且仅当任意两道相邻题目的难度之差的绝对值不超过 $k$（即 $\leq k$）时，该比赛被称为平衡的。

为了使剩余题目的某种排列方式构成一场平衡的比赛，你至少需要移除多少道题？

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The first line of each test case contains two positive integers $n$ ($1 \leq n \leq 2 \cdot 10^5$) and $k$ ($1 \leq k \leq 10^9$) — the number of problems, and the maximum allowed absolute difference between consecutive problems.

The second line of each test case contains $n$ space-separated integers $a_i$ ($1 \leq a_i \leq 10^9$) — the difficulty of each problem.

Note that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）—— 表示测试用例的数量。

每个测试用例的第一行包含两个正整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）和 $k$（$1 \leq k \leq 10^9$）—— 分别表示题目数量以及相邻题目难度允许的最大绝对差值。

每个测试用例的第二行包含 $n$ 个以空格分隔的整数 $a_i$（$1 \leq a_i \leq 10^9$）—— 表示每道题的难度。

注意：所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

For each test case, output a single integer — the minimum number of problems you have to remove so that an arrangement of problems is balanced.

对于每个测试用例，输出一个整数——即为使题目安排达到平衡所需移除的最少题目数量。

For the first test case, we can remove the first $2$ problems and construct a set using problems with the difficulties $[4, 5, 6]$, with difficulties between adjacent problems equal to $|5 - 4| = 1 \leq 1$ and $|6 - 5| = 1 \leq 1$.

For the second test case, we can take the single problem and compose a round using the problem with difficulty $10$.

对于第一个测试用例，我们可以移除前 $2$ 个题目，并使用难度为 $[4, 5, 6]$ 的题目构造一个题目集，相邻题目难度之差分别为 $|5 - 4| = 1 \leq 1$ 和 $|6 - 5| = 1 \leq 1$。

对于第二个测试用例，我们可以仅选取单个题目，并使用难度为 $10$ 的题目构造一场比赛。