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;
int a, b, c, d, e, zx, xc, za, i, j, ii, jj, k, f[1000009], pi, p[1000009][3],
    lf[1000009], rg[1000009], tim, seg[2500009], seg2[2500009], z, x, l, r,
    pas[1000009], pasi;
bool bo[1000009];
deque<pair<int, int> > de;
vector<int> v[1000009];
void dfs(int q, int w) {
  bo[q] = 1;
  tim++;
  lf[q] = rg[q] = tim;
  for (vector<int>::iterator it = v[q].begin(); it != v[q].end(); it++) {
    if ((*it) == w) continue;
    dfs((*it), q);
    if (rg[q] < rg[(*it)]) rg[q] = rg[(*it)];
  }
}
void pushdown() {
  if (p[pi][0] != p[pi][1]) {
    seg2[p[pi][2] * 2] += seg2[p[pi][2]];
    seg2[p[pi][2] * 2 + 1] += seg2[p[pi][2]];
  }
  seg[p[pi][2]] += seg2[p[pi][2]];
  seg2[p[pi][2]] = 0;
}
void upd() {
  pushdown();
  if (p[pi][0] > r || p[pi][1] < l) {
    pi--;
    return;
  }
  if (p[pi][0] >= l && p[pi][1] <= r) {
    seg2[p[pi][2]] += z;
    pushdown();
    pi--;
    return;
  }
  pi++;
  p[pi][0] = p[pi - 1][0];
  p[pi][1] = (p[pi - 1][0] + p[pi - 1][1]) / 2;
  p[pi][2] = p[pi - 1][2] * 2;
  upd();
  pi++;
  p[pi][0] = (p[pi - 1][0] + p[pi - 1][1]) / 2 + 1;
  p[pi][1] = p[pi - 1][1];
  p[pi][2] = p[pi - 1][2] * 2 + 1;
  upd();
  seg[p[pi][2]] = max(seg[p[pi][2] * 2], seg[p[pi][2] * 2 + 1]);
  pi--;
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> a >> k;
  for (i = 1; i <= a; i++) cin >> f[i];
  for (i = a; i >= 1; i--) {
    zx = 0;
    while (de.size() != 0) {
      if (de.front().first <= f[i]) {
        de.pop_front();
      } else {
        zx = de.front().second;
        break;
      }
    }
    de.push_front(make_pair(f[i], i));
    if (zx != 0) {
      v[zx].push_back(i);
    }
  }
  for (i = a; i >= 1; i--) {
    if (bo[i] == 1) continue;
    dfs(i, 0);
  }
  za = 1;
  while (za < a) za *= 2;
  for (i = a; i > a - k; i--) {
    pi = 1;
    p[pi][0] = 1;
    p[pi][1] = za;
    p[pi][2] = 1;
    l = lf[i];
    r = rg[i];
    z = 1;
    upd();
  }
  pi = 1;
  p[pi][0] = 1;
  p[pi][1] = za;
  p[pi][2] = 1;
  pushdown();
  pasi++;
  pas[pasi] = seg[1];
  for (i = a; i > k; i--) {
    pi = 1;
    p[pi][0] = 1;
    p[pi][1] = za;
    p[pi][2] = 1;
    l = lf[i];
    r = rg[i];
    z = -1;
    upd();
    pi = 1;
    p[pi][0] = 1;
    p[pi][1] = za;
    p[pi][2] = 1;
    l = lf[i - k];
    r = rg[i - k];
    z = 1;
    upd();
    pi = 1;
    p[pi][0] = 1;
    p[pi][1] = za;
    p[pi][2] = 1;
    pushdown();
    pasi++;
    pas[pasi] = seg[1];
  }
  for (i = pasi; i >= 1; i--) cout << pas[i] << " ";
  return 0;
}
