← 返回题目列表

AtCoder · awc0040_c

C. 苹果丰收

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

高桥正在果园帮忙收割苹果。果园有 N 苹果树排成一条直线,每棵树都种植在不同的位置。的 i- 第棵树位于坐标处 数轴上的 X_i 。

高桥使用收割车收集苹果。推车可以跨一段时间停放 [L, R] (L \leq R)在数轴上,他可以从该区间内的所有树上收获苹果。但是,小车可以覆盖的范围是有限制的:间隔的长度 R - L 最多必须是 K.

Takahashi 最多想选择单个长度区间 K 停放车并从尽可能多的树上收获苹果。

一棵树 i 在区间内 [L, R] 当且仅当 L \leq X_i \leq R.

确定可收获苹果的最大树数。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 0 \leq X_i \leq 10^9
  • X_i \neq X_j (i \neq j)
  • 所有输入均为整数

输入

N K
X_1 X_2 \ldots X_N
  • 第一行包含 N,苹果树的数量,以及 K,间隔长度的上限,以空格分隔。
  • 第二行包含每棵苹果树的坐标 X_1, X_2, \ldots, X_N,用空格分隔。

输出

在单行上打印最多可收获的苹果树数量,间隔长度最多 K.


示例输入 1

5 3
1 5 2 8 4

示例输出 1

3

示例输入 2

8 10
3 15 7 25 12 30 8 20

示例输出 2

4

示例输入 3

12 100
50 200 75 300 120 80 450 90 500 110 85 95

示例输出 3

8