题目描述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

出题Author

ftiasch

来源Source