The task is adapted from HDOJ 6701 - Make Rounddog Happy.
Bobo has a sequence of integers a1, a2, ... , an and an integer m.
Let f(j) be the number of i where 1 ≤ i ≤ j and max{ai, ... , aj} - (j - i + 1) ≥ m hold. Find the value of f(1), ... , f(n).
输入描述:
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 a1, a2, ... , an.
· 1 ≤ n ≤ 106
· -n ≤ m ≤ n
· 1 ≤ ai ≤ n
· The sum of n does not exceed 5×106
输出描述:
For each test case, print n integers f(1), ... , f(n).
示例1
输入
复制
3 0
1 3 2
3 1
1 3 2
5 2
1 2 3 4 5