1094 : Make Rounddog Very Happy

Description

The task is adapted from HDOJ 6701 - Make Rounddog Happy.

Bobo has a sequence of integers a₁, a₂, …, a_n and an integer m.

Let f(j) be the number of i where 1 ≤ i ≤ j and max {a_i, …, a_j} − (j − i + 1) ≥ m hold. Find the value of f(1), …, f(n).

Input

The input consists of several test cases terminated by end-of-file.

The first line of each test case contains two integers n and m, and the second line contains n integers a₁, a₂, …, a_n.

• 1 ≤ n ≤ 10⁶
•  − n ≤ m ≤ n
• 1 ≤ a_i ≤ n
• The sum of n does not exceed 5 × 10⁶.

Output

For each test case, print n integers f(1), …, f(n).

Sample

3 0
1 3 2
3 1
1 3 2
5 2
1 2 3 4 5

1 2 3
0 2 2
0 0 1 2 3

Hint

Source

Author

ftiasch