6503 - 数值靠近(close)

题目描述

给定 n 个整数,从中选择若干个数,要求所选数的最大值与最小值之差不超过 d。求最多可以选择多少个数。

所选位置不要求在原序列中连续。相同数值的不同位置可以分别选取。

输入

第一行输入两个整数 n,d。第二行输入 n 个整数 a_1,a_2,\ldots,a_n。

输出

输出一个整数,表示最多可以选择的数的个数。

样例

输入

6 2
8 3 5 4 12 5

输出

4

输入

12 5
20 4 11 7 4 9 14 6 8 25 10 5

输出

7

输入

30 8
40 13 27 9 18 15 44 21 16 12 33 17 19 14 50 20 11 23 25 18 10 31 22 16 28 7 24 26 15 39

输出

12
说明

样例说明 1

可以选择原序列第 2,3,4,6 个数,分别为 3,5,4,5。最大值与最小值之差为 5-3=2,共选出 4 个数。

两个 5 来自不同位置,可以同时选择。不能选出满足要求的 5 个数,因此答案为 4。

数据范围与提示

对于所有测试数据,保证:1\le n\le10^5,0\le d\le10^9,1\le a_i\le10^9。

本题共 10 个测试点,每个测试点 10 分,各测试点独立计分。

测试点编号n\le特殊性质
1 \sim 210无
3 \sim 410^3无
5 \sim 610^5A
7 \sim 1010^5无

特殊性质 A:d=0。

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 8
通过人数 6
金币数量 1 枚
难度 基础


上一题 下一题