← 返回题目列表

AtCoder · abc403_d

D. 禁止差异

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

分数: 425 点

问题陈述

给你一个长度-N 整数序列 A=(A_1,A_2,\dots,A_N) 和一个非负整数 D。 我们希望从中删除尽可能少的元素 A 获取序列 B 满足以下条件:

  • |B_i - B_j|\neq D 对于所有人 i,j \; (1 \leq i < j \leq |B|).

找出所需的最小删除次数。

约束

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

输入

输入由标准输入按以下格式给出:

N D
A_1 A_2 \dots A_N

输出

打印答案。


示例输入 1

5 2
3 1 4 1 5

示例输出 1

1

删除 A_1=3 产量 B=(1,4,1,5),满足 |B_i - B_j|\neq 2 对于所有人 i<j.


示例输入 2

4 3
1 6 1 8

示例输出 2

0

序列 A 可能已经满足条件。


示例输入 3

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

示例输出 3

2