#ABC326C. 高桥君的礼物
高桥君的礼物
AT_abc326_c [ABC326C] Peak
题目描述
高桥君在数轴上放置了 个礼物。其中,第 个礼物被放在坐标 上。
你可以选择数轴上的一个长度为 的半开区间 ,并获得所有落在该区间内的礼物。具体来说,获得礼物的步骤如下:
首先,选择一个实数 ;
然后,获得所有满足 的礼物。
请求出最多能获得多少个礼物。
输入格式
第一行输入两个整数 $n,m \left(1 \leqq n \leqq 3 \times 10^5;\ 1 \leqq m \leqq 10^9\right)$,代表礼物的数量和半开区间的长度。
第二行输入 个整数 $a_1,a_2,\dots,a_n \left(0 \leqq a_i \leqq 10^9\right)$,代表第 个礼物的坐标。
输出格式
在一行上输出一个整数,代表最多能获得的礼物数量。
测试样例
8 6
2 3 5 7 11 13 17 19
4
样例 1 解释
在这个样例中,指定半开区间 时,坐标为 的 个礼物都可以获得,这是可以获得的最大数量。
10 1
3 1 4 1 5 9 2 6 5 3
2
样例 2 解释
同一个坐标上也可能放有多个礼物。在这个样例中,指定半开区间 时,可以获得坐标为 的 个礼物,这就是可以获得的最大数量。
10 998244353
100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853
7