P17139 [KOI 2026 #1] Jumping

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

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 $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$).

### 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