#ABC326C. 高桥君的礼物

高桥君的礼物

AT_abc326_c [ABC326C] Peak

题目描述

\hspace{15pt}高桥君在数轴上放置了 nn 个礼物。其中,第 ii 个礼物被放在坐标 aia_i 上。

\hspace{15pt}你可以选择数轴上的一个长度为 mm 的半开区间 [x,x+m)[x,x+m),并获得所有落在该区间内的礼物。具体来说,获得礼物的步骤如下:

∙ \hspace{23pt}\bullet\,首先,选择一个实数 xx;

∙ \hspace{23pt}\bullet\,然后,获得所有满足 x≦ai<x+mx \leqq a_i < x+m 的礼物。

\hspace{15pt}请求出最多能获得多少个礼物。

输入格式

\hspace{15pt}第一行输入两个整数 $n,m \left(1 \leqq n \leqq 3 \times 10^5;\ 1 \leqq m \leqq 10^9\right)$,代表礼物的数量和半开区间的长度。

\hspace{15pt}第二行输入 nn 个整数 $a_1,a_2,\dots,a_n \left(0 \leqq a_i \leqq 10^9\right)$,代表第 ii 个礼物的坐标。

输出格式

\hspace{15pt}在一行上输出一个整数,代表最多能获得的礼物数量。

测试样例

8 6
2 3 5 7 11 13 17 19
4

样例 1 解释

\hspace{15pt}在这个样例中,指定半开区间 [1.5,7.5)[1.5,7.5) 时,坐标为 2,3,5,72,3,5,7 的 44 个礼物都可以获得,这是可以获得的最大数量。

10 1
3 1 4 1 5 9 2 6 5 3
2

样例 2 解释

\hspace{15pt}同一个坐标上也可能放有多个礼物。在这个样例中,指定半开区间 [1,2)[1,2) 时,可以获得坐标为 11 的 22 个礼物,这就是可以获得的最大数量。

10 998244353
100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853
7