For some array c, let's denote a greedy subsequence as a sequence of indices p_1, p_2, ..., p_l such that 1 ≤ p_1 < p_2 < ... < p_l ≤ |c|, and for each i ∈ [1, l - 1], p_{i + 1} is the minimum number such that p_{i + 1} > p_i and c[p_{i + 1}] > c[p_i].

You are given an array a_1, a_2, ..., a_n. For each its subsegment of length k, calculate the length of its longest greedy subsequence.

Input

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

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 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.

Examples

Input


6 4
1 5 2 5 3 6


Output


2 2 3 


Input


7 6
4 5 2 5 3 6 6


Output


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]). 
#include <bits/stdc++.h>
using namespace std;
struct node {
  long long nxt, to;
} o[1000010];
long long n, k, a[1000010], sta[1000010], top, head[1000010], I, s[1000010],
    sz[1000010], t[1000010 << 2], lz[1000010 << 2];
void read(long long& x) {
  x = 0;
  char s = getchar();
  while (s < '0' || s > '9') s = getchar();
  while (s >= '0' && s <= '9') x = (x << 3) + (x << 1) + s - 48, s = getchar();
}
void add(long long u, long long v) {
  o[++I] = (node){head[u], v};
  head[u] = I;
}
void bfs() {
  stack<long long> q;
  q.push(n);
  while (!q.empty()) {
    long long now = q.top();
    s[now] = ++s[0], q.pop();
    for (long long i = head[now]; i; i = o[i].nxt) q.push(o[i].to);
  }
}
long long max(long long a, long long b) { return a > b ? a : b; }
long long ls(long long id) { return id << 1; }
long long rs(long long id) { return id << 1 | 1; }
void up(long long id) { t[id] = max(t[ls(id)], t[rs(id)]); }
void down(long long id) {
  long long l = ls(id), r = rs(id);
  lz[l] += lz[id], lz[r] += lz[id];
  t[l] += lz[id], t[r] += lz[id];
  lz[id] = 0;
}
void pls(long long l, long long r, long long id, long long L, long long R,
         long long w) {
  if (L <= l && r <= R) {
    lz[id] += w, t[id] += w;
    return;
  }
  down(id);
  long long mid = l + r >> 1;
  if (L <= mid) pls(l, mid, ls(id), L, R, w);
  if (R > mid) pls(mid + 1, r, rs(id), L, R, w);
  up(id);
}
signed main() {
  read(n), read(k);
  for (long long i = 1; i <= n + 1; i++) sz[i] = 1;
  for (long long i = 1; i <= n; i++) {
    read(a[i]);
    while (a[i] > a[sta[top]] && top) sz[i] += sz[sta[top]], add(i, sta[top--]);
    sta[++top] = i;
  }
  while (top) sz[n + 1] += sz[sta[top]], add(n + 1, sta[top--]);
  n++, bfs();
  for (long long i = 1; i <= k; i++) pls(1, n, 1, s[i], s[i] + sz[i] - 1, 1);
  printf("%I64d ", t[1]);
  for (long long i = k + 1; i < n; i++) {
    pls(1, n, 1, s[i - k], s[i - k] + sz[i - k] - 1, -1);
    pls(1, n, 1, s[i], s[i] + sz[i] - 1, 1);
    printf("%I64d ", t[1]);
  }
  return 0;
}
