강변 도로의 임시 노선

문제

강변을 따라 곧게 뻗은 도로에서 임시 버스 노선을 운영하려 한다. 도로의 각 위치는 기준점에서 떨어진 거리를 나타내는 좌표로 표현한다. 행사 참가자들이 버스 탑승을 신청했으며, 각 참가자는 자신이 기다릴 위치를 하나 정했다. 여러 참가자가 같은 위치에서 기다릴 수도 있다. 임시 노선 하나는 출발 좌표 s를 정한 뒤 좌표가 커지는 방향으로 정확히 L만큼 운행한다. 따라서 이 노선이 담당할 수 있는 탑승 위치는 s 이상 s+L 이하인 모든 좌표다. 출발점과 종점에서 기다리는 참가자도 탑승할 수 있다. 출발 좌표 s는 0 이상 1,000,000,000 이하의 정수 중에서 자유롭게 정할 수 있다. 종점의 좌표가 1,000,000,000을 넘어도 운행할 수 있다. 버스의 정원과 정차 횟수에는 제한이 없다. 한 노선이 담당하는 구간 안에 있는 참가자는 인원수에 관계없이 모두 태울 수 있다. 참가자가 두 노선 이상의 운행 구간에 포함되어도 괜찮으며, 그중 어느 노선에 탑승하는지는 정할 필요가 없다. 필요한 조건은 모든 참가자의 탑승 위치가 적어도 한 노선의 운행 구간에 포함되는 것이다. 운영자는 이 조건을 만족하면서 임시 노선의 수를 가능한 한 적게 만들려고 한다. 서로 다른 노선의 운행 구간은 겹쳐도 된다. L이 0이면 한 노선은 출발 좌표와 같은 위치에서 기다리는 참가자만 태울 수 있다. 모든 참가자의 좌표가 주어질 때 필요한 노선 수의 최솟값을 구한다. 출력에서는 실제 출발 좌표나 참가자별 탑승 노선을 제시하지 않는다. 같은 최소 노선 수를 만드는 배치가 여러 개여도 그 공통된 최솟값만 출력한다.

입력

첫째 줄에 참가자 수 N과 노선의 운행 거리 L이 공백으로 구분되어 주어진다. N은 1 이상 100,000 이하의 정수이고, L은 0 이상 1,000,000,000 이하의 정수다.
둘째 줄에 각 참가자의 탑승 좌표를 나타내는 정수 N개가 공백으로 구분되어 주어진다. 각 좌표는 0 이상 1,000,000,000 이하이며, 정렬되어 있지 않을 수 있고 중복될 수 있다.

출력

모든 참가자를 태우는 데 필요한 임시 노선 수의 최솟값을 정수 하나로 출력한다. 주어진 조건에서는 항상 모든 참가자를 태울 수 있다.

7 4
9 1 5 13 5 20 17

3

5 0
8 8 2 2 8

2

4 10
10 0 7 10

1

출처: Devin.KR 자체 제작