한 번에 실을 택배

문제

택배 집하장에는 출발 준비가 끝난 상자 N개가 놓여 있다. 각 상자에는 배송 구역을 나타내는 정수 번호가 하나씩 붙어 있다. 같은 구역으로 가는 상자가 여러 개 있을 수 있으며, 구역 번호가 같더라도 서로 다른 상자로 취급한다. 상자가 놓인 순서는 도착 순서일 뿐이므로 차량에 실을 상자를 고를 때는 이 순서를 따를 필요가 없다. 운영 담당자는 이번 차량의 배송 범위를 좁게 유지하려고 한다. 이를 위해 차량에 실은 상자들의 구역 번호 중 최댓값과 최솟값의 차이가 K 이하가 되도록 정했다. 차량에 실을 수 있는 상자의 개수나 무게에는 다른 제한이 없다. 따라서 이 조건만 만족하면 원하는 상자를 모두 실을 수 있다. 상자를 하나만 고르면 최댓값과 최솟값이 같으므로 그 차이는 0이다. 예를 들어 K가 3이고 구역 번호가 2, 5, 5인 상자를 고르면 번호의 차이는 3이므로 함께 실을 수 있다. 반면 구역 번호가 2와 6인 상자를 함께 고르면 번호의 차이가 4이므로 조건을 만족하지 않는다. 두 상자의 번호가 서로 가깝다는 이유만으로 다른 모든 상자와 함께 실을 수 있는 것은 아니며, 반드시 고른 상자 전체의 최댓값과 최솟값을 비교해야 한다. 담당자는 조건을 지키면서 이번 차량에 가능한 한 많은 상자를 싣고자 한다. 입력으로 주어지는 모든 상자 중 일부를 골라 실을 때, 실을 수 있는 상자 개수의 최댓값을 구한다. 같은 개수를 만드는 선택이 여러 개라면 어느 선택을 사용해도 되며, 선택한 상자의 번호나 위치는 출력하지 않는다. N은 1 이상이고 K는 0 이상이므로 적어도 하나의 상자는 항상 실을 수 있다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000, 0 ≤ K ≤ 1,000,000,000이다.
다음 N개 줄에는 각 상자의 구역 번호 A_i가 하나씩 주어진다. A_i는 0 이상 1,000,000,000 이하의 정수이다. 같은 번호가 여러 번 주어질 수 있다.

출력

조건을 만족하도록 차량에 실을 수 있는 상자 개수의 최댓값을 정수 하나로 출력한다.

7 3
8
2
5
4
11
5
9

4

5 0
7
3
7
3
7

3

1 0
0

1

출처: Devin.KR 자체 제작