점프

이차원 좌표 평면에 $1$번부터 $N$번까지 번호가 부여된 $N$개의 발판이 있다. 각 발판은 좌표 평면 위의 한 점으로 표현할 수 있고, $i$ ($1 \le i \le N$)번 발판의 위치 좌표는 $\left( X_i, i \right)$이다.

두 정수 $i$, $j$ ($1 \le i, j \le N$)에 대해, 아래의 두 조건을 모두 만족할 때에만 $i$번 발판에서 $j$번 발판으로 이동할 수 있다.

• $i < j$
• $\left| X_i - X_j \right| \le D$

여기서, $D$는 주어지는 상수이며, 양의 정수 값을 가진다.

각 발판에 대하여, 그 발판에서 시작해서 다른 발판으로 이동하는 것을 $0$번 이상 반복하여 도달할 수 있는 서로 다른 발판의 개수를 세는 프로그램을 작성하라. 이 개수에는 그 발판 자기 자신도 포함되어야 함에 유의하라.

• 주어지는 모든 수는 정수이다.
• $1 \le N \le 300\,000$
• $1 \le D \le 10^9$
• 정수 $i$ ($1 \le i \le N$)에 대하여 $1 \le X_i \le 10^9$

1. (12점) $N \le 300$
2. (32점) $N \le 7\,500$
3. (9점) $X_1 \le X_2 \le \cdots \le X_N$
4. (23점) 정수 $i$ ($1 \le i \le N$)에 대하여 $X_i \le 30$
5. (33점) $D = 1$
6. (41점) 추가적인 제약 조건 없음.

첫 줄에 두 정수 $N$, $D$가 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 $N$개의 정수 $X_1, X_2, \cdots, X_N$이 공백으로 구분되어 차례대로 주어진다.

첫 줄에 $N$개의 정수를 공백으로 구분하여 출력한다. 이 중 $i$번째 정수는 $i$번 발판에서 시작해서 다른 발판으로 이동하는 것을 $0$번 이상 반복하여 도달할 수 있는 서로 다른 발판의 개수를 의미한다 ($1 \le i \le N$).