스마트 홈의 수신 창

문제

스마트 홈의 센서들은 정해진 시각에 상태 보고를 전송한다. 중앙 수신기는 평소에는 잠들어 있으며, 수신 창을 열어 둔 동안에만 보고를 받을 수 있다. 관리자는 하루 동안 예정된 모든 보고를 받으면서 수신 창을 여는 횟수를 최소화하려 한다. 보고가 전송되는 시각은 모두 미리 알려져 있지만 입력에는 시각순으로 정리되어 있지 않다. 수신 창을 정수 시각 s에 열면 s 이상 s+D 이하의 모든 시각에 전송되는 보고를 받을 수 있다. 양 끝 시각도 수신 범위에 포함된다. 예를 들어 D가 4이고 시각 7에 창을 열면 시각 7과 11의 보고를 모두 받을 수 있지만 시각 12의 보고는 받을 수 없다. 수신 창의 길이는 언제 열어도 같은 D이며, 보고를 받았다는 이유로 일찍 닫거나 수신 범위를 늘릴 수 없다. 수신 창을 여는 시각 s는 0 이상의 정수 중에서 자유롭게 선택한다. 센서의 보고 시각과 같아도 되고 달라도 된다. 창은 여러 번 열 수 있고, 서로 다른 창의 수신 범위가 겹쳐도 된다. 하나의 창은 범위 안에 들어오는 보고를 개수 제한 없이 받을 수 있다. 따라서 여러 센서가 같은 시각에 보고하더라도 그 시각을 포함하는 창 하나면 충분하다. 모든 보고는 적어도 하나의 수신 창에 포함되어야 하며, 보고를 누락하거나 전송 시각을 바꾸는 것은 허용되지 않는다. 보고가 하나 이상 주어지므로 항상 하나 이상의 창이 필요하고, 각 보고 시각에 창을 열면 언제나 모든 보고를 받을 수 있다. 최적의 창 배치가 여러 가지여도 배치 자체는 출력하지 않는다. 필요한 수신 창 개수의 최솟값만 구한다.

입력

첫째 줄에 보고 수 N과 수신 범위 길이 D가 공백으로 주어진다. N과 D는 정수이며 1≤N≤100000, 0≤D≤1000000000이다.
둘째 줄에 N개의 보고 시각 t가 공백으로 주어진다. 각 t는 0≤t≤1000000000인 정수이다. 시각은 중복될 수 있으며 임의의 순서로 주어진다.

출력

모든 보고를 받을 수 있는 수신 창 개수의 최솟값을 정수 하나로 출력한다.

7 4
12 3 7 11 3 18 16

3

5 0
9 2 9 2 9

2

4 10
10 0 5 10

1

출처: Devin.KR 자체 제작