기상 관측소에서 센서로 \(N\)개의 측정값을 기록했다. 센서에는 오차가 있어서, 두 측정값의 차이가 \(D\) 이하라면 사실상 같은 값일 수 있다고 본다.

측정값들을 다음 규칙으로 그룹으로 묶는다: 서로 다른 측정값들을 오름차순으로 늘어놓았을 때, 이웃한 두 값의 차이가 \(D\) 이하이면 두 값은 같은 그룹에 속한다. (이 관계가 연쇄되면 그 값들은 모두 한 그룹이다.)

그룹에는 가장 작은 값을 포함하는 그룹부터 차례대로 \(1, 2, 3, \dots\) 번호를 붙인다. 각 측정값이 속한 그룹 번호를 입력 순서대로 출력하여라.

• \(1 \le N \le 100\,000\)
• \(0 \le D \le 10^9\)
• 모든 측정값은 \(-10^9\) 이상 \(10^9\) 이하의 정수이다.

첫째 줄에 측정값의 수 \(N\)과 허용 오차 \(D\)가 공백으로 구분되어 주어진다.

둘째 줄에 측정값 \(N\)개가 공백으로 구분되어 주어진다.

각 측정값이 속한 그룹의 번호를 입력 순서대로 한 줄에 공백으로 구분해 출력한다.

riseoj 작성

출처 Original