AT_abc326_c [ABC326C] Peak

题目描述

高桥君在数轴上放置了 $N$ 个礼物。其中，第 $i$ 个礼物被放在坐标 $A_i$ 上。

你可以选择数轴上的一个长度为 $M$ 的半开区间 $[x, x+M)$，并获得所有落在该区间内的礼物。
具体来说，获得礼物的步骤如下：

• 首先，选择一个实数 $x$。
• 然后，获得所有满足 $x \leq A_i < x+M$ 的礼物。

你最多能获得多少个礼物？

输入格式

输入以如下格式从标准输入给出。

$N$ $M$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

请输出你最多能获得的礼物数量，作为一个整数。

输入输出样例 #1

输入 #1

8 6
2 3 5 7 11 13 17 19

输出 #1

4

输入输出样例 #2

输入 #2

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

输出 #2

2

输入输出样例 #3

输入 #3

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

输出 #3

7

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 3 \times 10^5$
• $1 \leq M \leq 10^9$
• $0 \leq A_i \leq 10^9$

样例解释 1

例如，指定半开区间 $[1.5, 7.5)$ 时，坐标为 $2, 3, 5, 7$ 的 $4$ 个礼物都可以获得，这是可以获得的最大数量。

样例解释 2

同一个坐标上也可能放有多个礼物。

由 ChatGPT 4.1 翻译