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

Bobo has a sequence of integers $a_1, a_2, \dots, a_n$ and an integer $m$.

Let $f(j)$ be the number of $i$ where $1 \leq i \leq j$ and $\max\{a_i, \dots, a_j\} - (j - i + 1) \geq m$ hold. Find the value of $f(1), \dots, 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_1, a_2, \dots, a_n$.

• $1 \leq n \leq 10^6$
• $-n \leq m \leq n$
• $1 \leq a_i \leq n$
• The sum of $n$ does not exceed $5 \times 10^6$.

Output

For each test case, print $n$ integers $f(1), \dots, f(n)$.

Sample Input

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

Sample Output

1 2 3
0 2 2
0 0 1 2 3