우편물 묶음의 구역 차이

문제

한 우체국에서는 발송할 우편물을 운반용 묶음으로 나누고 있다. 각 우편물에는 배달 구역을 나타내는 정수 번호가 하나씩 적혀 있다. 구역 번호는 0부터 999까지이며, 번호가 같더라도 서로 다른 우편물일 수 있다. 우편물의 무게와 크기는 모두 같아서 묶음에 넣을 수 있는 우편물 수에는 제한이 없다. 운반 담당자는 한 묶음에 들어 있는 우편물들의 구역 번호가 지나치게 벌어지는 것을 막으려 한다. 이를 위해 각 묶음에서 가장 큰 구역 번호와 가장 작은 구역 번호의 차이가 K 이하가 되도록 정했다. 우편물이 하나만 들어 있는 묶음에서는 이 차이를 0으로 계산한다. 같은 구역의 우편물만 들어 있는 묶음도 차이가 0이므로 항상 조건을 만족한다. 모든 우편물은 정확히 하나의 묶음에 들어가야 한다. 우편물을 버리거나 복사할 수 없으며, 우편물이 하나도 없는 빈 묶음은 만들지 않는다. 입력에 주어진 순서는 접수 순서일 뿐이므로, 묶음을 만들기 전에 우편물을 원하는 순서로 자유롭게 재배치할 수 있다. 구역 번호가 같은 우편물들을 반드시 같은 묶음에 넣어야 한다는 조건은 없다. 우체국은 묶음마다 별도의 표찰을 붙이므로, 조건을 지키면서 묶음의 수를 가능한 한 적게 만들려고 한다. 예를 들어 구역 번호가 1, 4, 7인 세 우편물을 생각하자. K가 3이면 1과 4를 함께 넣을 수 있고 4와 7도 함께 넣을 수 있다. 그러나 세 우편물을 모두 같은 묶음에 넣으면 최댓값과 최솟값의 차이가 6이므로 허용되지 않는다. 묶음 안에서 이웃한 번호의 차이만 확인해서는 안 된다. 우편물의 구역 번호와 K가 주어졌을 때 필요한 묶음 수의 최솟값을 구하는 프로그램을 작성하라. 최적의 묶음 구성이 여러 가지여도 그 구성 자체는 출력하지 않는다. 우편물을 하나씩 묶으면 항상 조건을 만족하므로 답은 반드시 존재한다.

입력

첫째 줄에 우편물 수 N과 허용하는 구역 번호 차이 K가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 0 ≤ K ≤ 999)
둘째 줄에 각 우편물의 구역 번호를 나타내는 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. (0 ≤ A_i ≤ 999)
입력으로 주어지는 모든 수는 정수다.

출력

조건을 만족하도록 모든 우편물을 나누는 데 필요한 묶음 수의 최솟값을 한 줄에 출력한다.

7 3
8 1 4 2 9 5 12

3

6 0
7 2 7 2 9 7

3

4 999
0 999 500 12

1

출처: Devin.KR 자체 제작