Problem Description

Elephant is playing the Big Fish Eat Small Fish game. Initially, there are $n$ fish lined up in a row in order of indices $1$ to $n$, and each fish has a size value (a positive integer) $a_i$.

A big fish can eat a small fish, but only if the size difference is large enough. There is a fixed parameter (a non-negative integer) $k$.

Elephant can control one fish to eat one adjacent fish (with no other fish between them). There are two ways to eat:

1. Eat directly: the controlled fish's size must be no smaller than the eaten fish's size, and the size difference must be at least $k$. That is, a fish of size $x$ can eat a fish of size $y$ directly if and only if $x-y\ge k$.
2. Use one tool: ignore the size difference and eat one fish.

After eating, the eaten fish disappears, and the controlled fish's size increases by the eaten fish's size. The relative order of fish positions does not change.

Elephant wants to know: for each $i$, if he controls fish $i$ to eat all other fish, what is the minimum number of tools needed.

Input Format

Note: Due to Luogu's judging limitations, when submitting this problem on Luogu, please use standard input/output, and do not use file input/output.

The first line contains two non-negative integers $n, k$, separated by spaces.

The second line contains $n$ positive integers $a_i$ separated by spaces, describing the initial size of each fish in order from index $1$ to $n$.

Output Format

Output one line with $n$ non-negative integers separated by spaces. The $i$-th integer is the answer for each $i$, i.e., the minimum number of tools needed for fish $i$ to eat all fish.

5 4
5 6 5 1 2

1 1 1 2 3

5 3
6 4 2 2 6

1 1 2 1 0

Hint

Constraints

For all testdata, $1 \leq n \leq 5 \times 10^6$, $0 \leq k \leq 10^9$, $1 \leq a_i \leq 10^9$.

For $10\%$ of the testdata, $n \leq 20$.

For another $10\%$ of the testdata, $n \leq 2000$.

For another $15\%$ of the testdata, $n \leq 2 \times 10^5$, $k = 0$.

For another $15\%$ of the testdata, $n \leq 2 \times 10^5$, $k \leq 10$.

For another $15\%$ of the testdata, $n \leq 2 \times 10^5$.

Note that this problem uses bundled subtasks.

Translated by ChatGPT 5