C - りんご収穫 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は果樹園でりんごの収穫作業を手伝っています。果樹園には N 本のりんごの木が一直線上に並んでおり、それぞれの木は異なる位置に植えられています。 i 番目の木は数直線上の座標 X_i の位置にあります。

高橋君は収穫用のカートを使ってりんごを集めます。カートは数直線上の区間 [L, R]（ L \leq R ）にまたがって停めることができ、その区間内にあるすべての木からりんごを収穫できます。ただし、カートがカバーできる範囲には制限があり、区間の長さ R - L は K 以下でなければなりません。

高橋君は、長さが K 以下の区間を 1 つ選んでカートを停め、できるだけ多くの木からりんごを収穫したいと考えています。

木 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
  • 1 行目には、りんごの木の本数を表す N と、区間の長さの上限を表す K が、スペース区切りで与えられる。
  • 2 行目には、各りんごの木の座標を表す X_1, X_2, \ldots, X_N が、スペース区切りで与えられる。

出力

長さが K 以下の区間で収穫できるりんごの木の最大本数を 1 行で出力してください。

入力例 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

Score : 366 pts

Problem Statement

Takahashi is helping with the apple harvest at an orchard. The orchard has N apple trees lined up in a straight line, each planted at a distinct position. The i-th tree is located at coordinate X_i on the number line.

Takahashi uses a harvesting cart to collect apples. The cart can be parked spanning an interval [L, R] (L \leq R) on the number line, and he can harvest apples from all trees within that interval. However, there is a limit on the range the cart can cover: the length of the interval R - L must be at most K.

Takahashi wants to choose a single interval of length at most K to park the cart and harvest apples from as many trees as possible.

A tree i is within the interval [L, R] if and only if L \leq X_i \leq R.

Determine the maximum number of trees from which apples can be harvested.

Constraints

  • 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)
  • All inputs are integers

Input

N K
X_1 X_2 \ldots X_N
  • The first line contains N, the number of apple trees, and K, the upper limit on the interval length, separated by a space.
  • The second line contains the coordinates of each apple tree X_1, X_2, \ldots, X_N, separated by spaces.

Output

Print on a single line the maximum number of apple trees that can be harvested with an interval of length at most K.

Sample Input 1

5 3
1 5 2 8 4

Sample Output 1

3

Sample Input 2

8 10
3 15 7 25 12 30 8 20

Sample Output 2

4

Sample Input 3

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

Sample Output 3

8