← 返回题目列表

Codeforces · 940/A

A. 点上线

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

我们没有测试用例。一场盛大的奥林匹克运动会即将来临。但问题提出者的首要任务应该是在这一轮中添加另一个问题。

线上多组点的直径是该组中两点之间的最大距离。例如,多重集{1,3,2,1}的直径为2。

由一个点组成的多重集的直径为 0。

线上有 n 个点。为了使剩余点的多重集的直径不超过 d,您必须删除的最少点数是多少?

输入

第一行包含两个整数 n 和 d (1 ≤ n ≤ 100, 0 ≤ d ≤ 100)——分别是点数和允许的最大直径。

第二行包含 n 个空格分隔的整数 (1 ≤ xi ≤ 100) - 点的坐标。

输出

输出一个整数 - 您必须删除的最少点数。

示例

输入 #1

3 1
2 1 4

输出 #1

1

输入 #2

3 0
7 7 7

输出 #2

0

输入 #3

6 3
1 3 4 6 9 10

输出 #3

3

注意

在第一个测试用例中,最佳策略是删除坐标为 4 的点。其余点将具有坐标 1 和 2,因此直径将等于 2 - 1 = 1。

在第二个测试用例中,直径等于 0,因此无需删除任何点。

在第三个测试用例中,最佳策略是删除坐标为 1、9 和 10 的点。其余点的坐标为 3、4 和 6,因此直径将等于 6 - 3 = 3。