分数: 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