题目描述

艾莉芬在玩大鱼吃小鱼游戏。初始有 $n$ 条鱼按编号 $1$ 到 $n$ 顺序排成一排，每条鱼有一个体型值（正整数）$a_i$。

大鱼可以吃小鱼，但必须体型差足够大才行，有一个固定的参数（非负整数） $k$。

艾莉芬可以控制一条鱼吃掉相邻（两条鱼位置之间没有其他鱼）的一条鱼，有两种吃法：

1. 直接吃，需要控制的鱼的体型不小于被吃的鱼且体型之差至少 $k$；即，体型 $x$ 的鱼能直接吃体型 $y$ 的鱼当且仅当 $x-y\ge k$。
2. 使用一次道具，无视体型差吃一条鱼；

吃之后，被吃的鱼会消失，控制的鱼的体型会加上被吃的鱼的体型。鱼的位置的先后顺序不会变。

艾莉芬想知道：对于每个 $i$，他控制 $i$ 号鱼吃完所有其他鱼最少要用几次道具。

输入格式

注：由于洛谷的评测限制，在洛谷上提交本题请使用标准输入输出，不要使用文件输入输出。

第一行两个非负整数 $n, k$，空格分隔。

第二行 $n$ 个空格分隔的正整数 $a_i$ 按编号 $1$ 到 $n$ 顺序依次表示每条鱼初始的体型。

输出格式

一行 $n$ 个用空格分隔的非负整数依次表示每个 $i$ 的答案，也就是让 $i$ 号鱼吃完所有鱼最少要用的道具数。

5 4
5 6 5 1 2

1 1 1 2 3

5 3
6 4 2 2 6

1 1 2 1 0

提示

【测试点约束】

对于所有数据，$1 \leq n \leq 5 \times 10^6$, $0 \leq k \leq 10^9$, $1 \leq a_i \leq 10^9$。

对于 $10\%$ 的数据，$n \leq 20$

对于另外 $10\%$ 的数据，$n \leq 2000$

对于另外 $15\%$ 的数据，$n \leq 2 \times 10^5$, $k = 0$

对于另外 $15\%$ 的数据，$n \leq 2 \times 10^5$, $k \leq 10$

对于另外 $15\%$ 的数据，$n \leq 2 \times 10^5$

注意本题有子任务捆绑测试。