Counting the Number of Non‐movable Operations

You are given a sequence of n integers \(a_1, a_2, \dots, a_n\). The rank of an element \(a_i\) is defined as

[ \text{rank}(a_i)= #{j \mid a_j > a_i}+1. ]

You are also given a constant \(k\). We perform the following operation repeatedly:

• Before each operation, an element \(a_i\) is said to be movable if, after increasing only \(a_i\) by \(k\) (and leaving all other elements unchanged), its rank remains the same. Otherwise, \(a_i\) is non‐movable.
• Then, in this operation, all movable numbers are increased by \(k\) simultaneously.

It can be proved that after a finite number of operations, every element of \(a\) will become movable, and from that point on every subsequent operation will have the property that every element is movable. In other words, the number of operations in which a given element is non‐movable is finite.

Your task is to determine, for each element in the original sequence (in the given order), the total number of operations in which it remains non‐movable, when the operations are performed for a long time (i.e. until stabilization).

Hint: An element \(a_i\) is movable if and only if there is no element \(a_j\) (with \(j \neq i\)) satisfying

[ a_i < a_j \le a_i+k, ]

so that you may notice that if the elements are sorted then an element will be blocked by its closest larger neighbor whose value is within \(k\) units. For elements having the same value, note that equality does not affect the rank.

inputFormat

The first line contains two integers \(n\) and \(k\) (\(1 \le n \le 10^5\), \(1 \le k \le 10^9\)).

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)).

outputFormat

Output a single line containing \(n\) integers. The \(i\)-th integer should be the total number of operations in which \(a_i\) is non‐movable, assuming that the operations are carried out until stabilization.

sample

3 3
1 2 4

2 1 0