题目描述

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\dots,A_N)$，以及一个非负整数 $D$。

你需要从序列 $A$ 中删除尽可能少的元素，得到一个新序列 $B$，使得它满足以下条件：

对于任意的 $1 \le i < j \le |B|$，都有：

也就是说，序列 $B$ 中任意两个不同位置上的元素之差的绝对值都不能等于 $D$。

请你求出最少需要删除多少个元素。

输入格式

第一行包含两个整数：

第二行包含 $N$ 个整数：

输出格式

输出一个整数，表示最少删除的元素个数。

输入输出样例

输入 #1

5 2
3 1 4 1 5

输出 #1

1

说明 #1

删除 $A_1=3$ 后，可以得到：

此时对于所有 $i<j$，都满足：

因此最少删除 $1$ 个元素。

输入 #2

4 3
1 6 1 8

输出 #2

0

说明 #2

原序列 $A$ 本身就已经满足条件，因此不需要删除任何元素。

输入 #3

10 3
1 6 2 10 2 3 2 10 6 4

输出 #3

2

数据范围

• $1 \le N \le 2 \times 10^5$
• $0 \le D \le 10^6$
• $0 \le A_i \le 10^6$
• 所有输入均为整数