题目描述

在二维坐标平面上有 $N$ 个踏板，编号为 $1$ 到 $N$。每个踏板都可以表示为坐标平面上的一个点。对于每个整数 $i$（$1 \le i \le N$），踏板 $i$ 的坐标为 $(X_i,i)$。

对于两个整数 $i,j$（$1 \le i,j \le N$），当且仅当以下两个条件均满足时，才能从踏板 $i$ 移动到踏板 $j$：

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

其中，$D$ 是给定的常数，并且是一个正整数。

请编写一个程序，对于每个踏板，计算从该踏板出发，经过 $0$ 次或多次从一个踏板到另一个踏板的移动后，能够到达的不同踏板数量。请注意，该数量应当包含作为起点的踏板本身。

输入格式

第一行输入两个整数 $N$ 和 $D$，整数之间以空格分隔。

第二行输入 $N$ 个整数 $X_1,X_2,\ldots,X_N$，整数之间以空格分隔。

输出格式

第一行输出 $N$ 个整数，整数之间以空格分隔。其中，第 $i$ 个整数表示从踏板 $i$ 出发，经过 $0$ 次或多次从一个踏板到另一个踏板的移动后，能够到达的不同踏板数量（$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

提示

样例说明 1

对于每个踏板，从该踏板出发能够到达的踏板如下：

• 踏板 $1$：能够到达包括踏板 $1$ 本身在内的所有踏板。
• 踏板 $2$：能够到达踏板 $2$、$3$、$4$、$6$。
• 踏板 $3$：能够到达踏板 $3$、$4$、$6$。
• 踏板 $4$：除踏板 $4$ 本身外，无法到达其他任何踏板。
• 踏板 $5$：能够到达踏板 $5$、$6$。
• 踏板 $6$：除踏板 $6$ 本身外，无法到达其他任何踏板。

限制条件

• 输入中给出的所有数均为整数。
• $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$ 分）无附加限制。

译注：没有单独的子任务 5 的测试点，所以子任务 6 有 $74$ 分。

翻译由 ChatGPT-5.6 完成