Problem Description

There are $N$ platforms on a 2D coordinate plane, numbered from $1$ to $N$. Each platform can be represented as a point on the plane. For each integer $i$ ($1 \le i \le N$), the coordinates of platform $i$ are $(X_i,i)$.

For two integers $i,j$ ($1 \le i,j \le N$), you can move from platform $i$ to platform $j$ if and only if both of the following conditions are satisfied:

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

Here, $D$ is a given constant and is a positive integer.

Write a program that, for each platform, computes the number of distinct platforms that can be reached starting from that platform after making $0$ or more moves from one platform to another. Note that this number should include the starting platform itself.

Input Format

The first line contains two integers $N$ and $D$, separated by spaces.

The second line contains $N$ integers $X_1,X_2,\ldots,X_N$, separated by spaces.

Output Format

Output $N$ integers on one line, separated by spaces. The $i$-th integer represents the number of distinct platforms that can be reached starting from platform $i$ after making $0$ or more moves from one platform to another ($1 \le i \le N$).

6 2
3 5 4 6 1 3

6 4 3 1 2 1

6 3
1 4 8 9 10 15

2 1 3 2 1 1

3 2
1 4 7

1 1 1

Hint

Sample Explanation 1

For each platform, the platforms reachable from it are as follows:

• Platform $1$: can reach all platforms, including platform $1$ itself.
• Platform $2$: can reach platforms $2$, $3$, $4$, and $6$.
• Platform $3$: can reach platforms $3$, $4$, and $6$.
• Platform $4$: cannot reach any other platform except platform $4$ itself.
• Platform $5$: can reach platforms $5$ and $6$.
• Platform $6$: cannot reach any other platform except platform $6$ itself.

Constraints

• All numbers in the input are integers.
• $1 \le N \le 300\,000$.
• $1 \le D \le 10^9$.
• For each integer $i$ ($1 \le i \le N$), $1 \le X_i \le 10^9$.

Subtasks

1. ($12$ points) $N \le 300$.
2. ($32$ points) $N \le 7\,500$.
3. ($9$ points) $X_1 \le X_2 \le \cdots \le X_N$.
4. ($23$ points) For each integer $i$ ($1 \le i \le N$), $X_i \le 30$.
5. ($33$ points) $D=1$.
6. ($41$ points) No additional constraints.

Translator's note: There are no separate testdata points for subtask 5, so subtask 6 is worth $74$ points.

Translated by ChatGPT-5.6.

Translated by ChatGPT 5