题目描述

Luke 喜欢吃东西。现在他面前有 $n$ 堆食物排成一行，第 $i$ 堆有 $a_i$ 单位的食物。

Luke 将从第 $1$ 堆走向第 $n$ 堆，他想要吃掉每一堆食物且不能回头。当 Luke 走到第 $i$ 堆时，只有当 $|v - a_i| \leq x$ 时他才能吃掉这堆食物，其中 $x$ 是一个固定的整数，$v$ 是 Luke 的“食物亲和力”。

在开始行走之前，Luke 可以将 $v$ 设置为任意整数。此外，对于每个 $i$（$1 \leq i \leq n$），在吃第 $i$ 堆食物之前，Luke 可以将他的食物亲和力 $v$ 改为任意整数。

请你求出，为了吃掉所有的食物，最少需要改变多少次食物亲和力。

注意，初始选择 $v$ 的操作不计入改变次数。

输入格式

输入包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。接下来是每组测试数据的描述。

对于每组测试数据，第一行包含两个整数 $n, x$（$1 \leq n \leq 2 \cdot 10^5$，$1 \leq x \leq 10^9$），分别表示食物堆的数量和 Luke 能吃下食物堆的最大差值。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$）。

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

输出格式

对于每组测试数据，输出一个整数，表示最少需要改变多少次食物亲和力。每个答案占一行。

说明/提示

在第一个测试用例中，Luke 可以在开始行走前将 $v$ 设为 $5$，然后可以直接吃掉所有食物，无需改变 $v$。

在第二个测试用例中，Luke 可以在开始行走前将 $v$ 设为 $3$，在吃第二堆食物前将 $v$ 改为 $10$，之后无需再改变 $v$。

在第四个测试用例中，Luke 可以在开始行走前将 $v$ 设为 $3$，在吃第六堆食物前将 $v$ 改为 $8$，之后无需再改变 $v$。

在第五个测试用例中，Luke 可以在开始行走前将 $v$ 设为 $4$，在吃第四堆食物前将 $v$ 改为 $6$，在吃第七堆食物前将 $v$ 改为 $12$，之后无需再改变 $v$。

由 ChatGPT 4.1 翻译

样例

7
5 3
3 8 5 6 7
5 3
3 10 9 8 7
12 8
25 3 3 17 8 6 1 16 15 25 17 23
10 2
1 2 3 4 5 6 7 8 9 10
8 2
2 4 6 8 6 4 12 14
8 2
2 7 8 9 6 13 21 28
15 5
11 4 13 23 7 10 5 21 20 11 17 5 29 16 11

0
1
2
1
2
4
6