주차장 안내 신호기

문제

길게 뻗은 주차장의 한쪽 통로에 안내가 필요한 지점들이 있다. 관리자는 이 지점들에 안내 신호가 도달하도록 임시 신호기를 설치하려 한다. 통로는 하나의 직선으로 생각하며, 각 지점의 위치는 통로 시작점을 기준으로 한 정수 좌표로 표시한다. 여러 안내 지점이 같은 좌표에 있을 수도 있다. 신호기 하나를 정수 좌표 s에 설치하면 좌표가 s 이상 s+L 이하인 모든 안내 지점에 신호가 도달한다. 두 끝점에 있는 지점도 포함한다. 신호는 좌표가 증가하는 방향으로만 전달되므로 s보다 작은 좌표에는 도달하지 않는다. 모든 신호기는 같은 길이 L을 사용하며, 설치한 뒤 길이나 방향을 바꿀 수 없다. L이 0이면 설치 좌표와 정확히 같은 위치에 있는 지점들에만 신호가 도달한다. 신호기는 안내 지점이 없는 곳에도 설치할 수 있다. 설치 가능한 좌표는 0 이상 10^9 이하의 모든 정수이며, 신호가 도달하는 오른쪽 끝 좌표가 10^9보다 커지는 것은 허용한다. 설치 위치에 따른 비용 차이나 설치 개수의 사전 제한은 없다. 신호기끼리 영향을 주지 않으므로 신호가 도달하는 구간들이 서로 겹쳐도 된다. 같은 안내 지점에 여러 신호기의 신호가 도달해도 추가 이득은 없다. 관리자의 목표는 모든 안내 지점에 적어도 하나의 신호가 도달하도록 하면서 설치하는 신호기의 개수를 최소화하는 것이다. 지점이 입력된 순서는 통로 위의 실제 순서와 무관하며, 같은 좌표가 반복되어도 그 위치를 여러 번 따로 덮을 필요는 없다. 최소 개수를 달성하는 설치 방법이 여러 가지라면 어느 방법을 택해도 되지만 설치 좌표 자체는 출력하지 않는다. 안내 지점의 좌표들과 신호 길이가 주어졌을 때 필요한 신호기의 최소 개수를 구한다.

입력

첫째 줄에 정수 N과 L이 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000, 0 ≤ L ≤ 10^9이다.
둘째 줄에 안내 지점의 좌표를 나타내는 정수 X_1, X_2, ..., X_N이 공백으로 구분되어 주어진다. 0 ≤ X_i ≤ 10^9이다. 좌표는 정렬되어 있지 않을 수 있으며 중복될 수 있다.

출력

모든 안내 지점에 신호가 도달하게 하는 신호기의 최소 개수를 정수 하나로 출력한다. 주어진 조건에서는 항상 설치할 수 있다.

7 3
9 1 4 8 12 4 16

4

5 0
3 3 0 8 0

3

4 10
10 0 7 10

1

출처: Devin.KR 자체 제작