← 返回题目列表

Codeforces · 990/B

B. 微观世界

中文机器翻译题面 查看原题

你有一个装有细菌的培养皿,你正准备潜入严酷的微观世界。但不幸的是,你附近没有显微镜,所以你无法观察它们。

您知道培养皿中有 $$$n$$$ 个细菌,第 $$$i$$$ 个细菌的大小为 $$$a_i$$$。你也知道星际正整数常数$$$K$$$。

当且仅当 $$$a_i > a_j$$$ 且 $$$a_i \le a_j + K$$$ 时,第 $$$i$$$ 个细菌才能吞噬第 $$$j$$$ 个细菌。第 $$$j$$$ 个细菌消失,但第 $$$i$$$ 个细菌没有改变其大小。这种细菌可以进行多次吞咽。在每次吞咽操作中,如果 $$$a_i > a_j$$$ 且 $$$a_i \le a_j + K$$$,任何细菌 $$$i$$$ 都可以吞咽任何细菌 $$$j$$$。吞咽行动一个接一个地进行。

例如,细菌大小的序列$$$a=[101, 53, 42, 102, 101, 55, 54]$$$ 和$$$K=1$$$。可能的燕子序列之一是: $$$[101, 53, 42, 102, \underline{101}, 55, 54]$$$ $$$\to$$$ $$$[101, \underline{53}, 42, 102, 55, 54]$$$ $$$\to$$$ $$$[\underline{101}, 42, 102, 55, 54]$$$ $$$\到$$$ $$$[42, 102, 55, \下划线{54}]$$$ $$$\到$$$ $$$[42, 102, 55]$$$。培养皿中总共残留有 $$$3$$$ 细菌。

由于您没有显微镜,您只能猜测,当您最终找到显微镜时,培养皿中可能残留的细菌数量最少是多少。

输入

第一行包含两个空格分隔的正整数 $$$n$$$ 和 $$$K$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le K \le 10^6$$$) — 细菌数量和星系间常数 $$$K$$$。

第二行包含 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — 细菌的大小。

输出

打印唯一的整数 - 可以保留的最小可能数量的细菌。

示例

输入 #1

7 1
101 53 42 102 101 55 54

输出 #1

3

输入 #2

6 5
20 15 10 15 20 25

输出 #2

1

输入 #3

7 1000000
1 1 1 1 1 1 1

输出 #3

7

注意

第一个例子在问题陈述中得到了澄清。

在第二个例子中,最佳的吞咽顺序是: $$$[20, 15, 10, 15, \underline{20}, 25]$$$ $$$\to$$$ $$$[20, 15, 10, \underline{15}, 25]$$$ $$$\to$$$ $$$[20, 15, \underline{10}, 25]$$$ $$$\到$$$ $$$[20, \underline{15}, 25]$$$ $$$\到$$$ $$$[\underline{20}, 25]$$$ $$$\到$$$ $$$[25]$$$。

在第三个例子中,没有细菌可以吞噬任何其他细菌。