No submission language available for this problem.

Description

Input

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 10^6$) — the length of array $a$ and the length of subsegments.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — array $a$.

Output

Print $n - k + 1$ integers — the maximum lengths of greedy subsequences of each subsegment having length $k$. The first number should correspond to subsegment $a[1..k]$, the second — to subsegment $a[2..k + 1]$, and so on.

Samples

6 4
1 5 2 5 3 6

2 2 3

7 6
4 5 2 5 3 6 6

3 3

Note

In the first example:

• $[1, 5, 2, 5]$ — the longest greedy subsequences are $1, 2$ ($[c_1, c_2] = [1, 5]$) or $3, 4$ ($[c_3, c_4] = [2, 5]$).
• $[5, 2, 5, 3]$ — the sequence is $2, 3$ ($[c_2, c_3] = [2, 5]$).
• $[2, 5, 3, 6]$ — the sequence is $1, 2, 4$ ($[c_1, c_2, c_4] = [2, 5, 6]$).

In the second example:

• $[4, 5, 2, 5, 3, 6]$ — the longest greedy subsequences are $1, 2, 6$ ($[c_1, c_2, c_6] = [4, 5, 6]$) or $3, 4, 6$ ($[c_3, c_4, c_6] = [2, 5, 6]$).
• $[5, 2, 5, 3, 6, 6]$ — the subsequence is $2, 3, 5$ ($[c_2, c_3, c_5] = [2, 5, 6]$).