#NC19487. Eustia of the Tarnished Wings

Eustia of the Tarnished Wings

题目描述

Novus Aither是一个潜藏着多个势力的城市。每个势力都有一个唯一的领导人,每个领导人有一个属性值。如果两个势力的领导人的属性值分别为a,b,且|a-b| ≤ m,说明这两个领导人的思想有一定的相似之处,这两个势力可以合并,新的领导人可以指定为原来的两个领导人中的任意一个。新产生的势力可以依照相同的规则,继续与其他势力合并。问在所有可能的情况中,最少会剩下几个势力。

输入格式

第一行两个空格隔开的整数 nn、mm,其中 1≤n≤1061\leq n\leq10^6,0≤m≤1090\leq m\leq10^9。nn 代表当前势力的个数,mm 的含义如题目描述。

第二行 nn 个空格隔开的整数 did_i,其中 0≤di≤1090\leq d_i\leq10^9,代表第 ii 个势力的领导人的属性值。

输出格式

输出一个数表示势力的最少数量。

样例 1

4 1
2 1 3 10
2

来源

牛客原题