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.

题目描述

在社交平台的兴趣社区运营中，系统需要根据用户的兴趣标签对用户进行分组管理，以优化内容推荐和互动体验。每个用户被分配一个整数类型的兴趣标签（例如，$0$表示“科技”，$1$表示“旅游”，$2$表示“美食”等），若两个用户的标签差值恰好为 $d$，则认为他们的兴趣存在较强冲突（例如，“编程”与“设计”的标签差值为 $1$，可能因资源竞争导致社区讨论混乱）。

运营团队希望从一个初始用户列表 $a$ 中删除最少的用户，使得剩余用户组成的社区 $b$ 中，任意两人的兴趣标签差值均不为 $d$。这一需求等价于在保留尽可能多用户的前提下，消除所有标签差值为 $d$ 的用户对，从而构建一个低冲突的兴趣社区。

简单的说 给定一个长度为 $n$ 的整数序列 $a=a_1,a_2,\dots,a_N$ 和一个非负整数 $d$ 。我们希望从 $a$ 中删除尽可能少的元素，以获得满足以下条件的序列 $b$ ：

• $|b_i - b_j|\neq d$ 对于所有 $i,j , (1 \leq i \lt j \leq |b|)$ 。

查找所需的最小删除数。

输入格式

第一行：两个整数 $n$ 和 $d$ $(1 \le n \le 10^6)$，$(0 \le d \le 10^6）$

第二行：$n$ 个整数 $(a_1, a_2, \dots, a_n)$（每个元素满足 $( 0 \le A_i \le 10^6）$。

输出格式

一个整数，表示需要删除的最少用户数。

样例

输入

5 2
3 1 4 1 5

输出

1

样例提示

删除 $a_1=3$ 将生成 $b=(1,4,1,5)$ ，它满足所有 $i \lt j$ 的 $|b_i - b_j|\neq 2$ 。

限制与约定

对于 $40\%$的数据，保证 $(1 \le n \le 100)$，$(0 \le d \le 100）$ （每个元素满足 $( 0 \le a_i \le 10^3）$。

对于 $100 \%$的数据， 保证 $(1 \le n \le 10^6)$，$(0 \le d \le 10^6）$ （每个元素满足 $( 0 \le a_i \le 10^6）$。

• 时间限制: $2 s$
• 空间限制: $256 MB$