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;
const long double eps = 1e-13;
const long double PI = acos(-1);
const int INF = (int)1e9 + 7;
const long long INFF = (long long)1e18;
const int mod = (int)1e9 + 7;
const int MXN = (int)1e6 + 7;
int a[MXN], siz[MXN], gp[MXN], pos[MXN];
vector<int> mem[MXN];
int fd(int v) { return gp[v] == v ? v : gp[v] = fd(gp[v]); }
void go(int v, int p) {
  reverse(begin(mem[v]), end(mem[v]));
  for (int x : mem[v]) {
    pos[x] = p;
    go(x, p - 1);
    p -= siz[x];
  }
}
struct Seg {
  int ll[MXN << 2], rr[MXN << 2], v[MXN << 2], d[MXN << 2];
  void bd(int l, int r, int p = 1) {
    ll[p] = l, rr[p] = r, v[p] = -INF;
    if (l == r) return;
    int mid = (l + r) >> 1;
    bd(l, mid, p << 1);
    bd(mid + 1, r, p << 1 | 1);
  }
  inline void pushdown(int p) {
    d[p << 1] += d[p];
    d[p << 1 | 1] += d[p];
    v[p << 1] += d[p];
    v[p << 1 | 1] += d[p];
    d[p] = 0;
  }
  int qy() { return v[1]; }
  void md1(int pp, int val, int p = 1) {
    if (ll[p] == rr[p]) {
      v[p] = val;
      return;
    }
    pushdown(p);
    int mid = (ll[p] + rr[p]) >> 1;
    if (pp <= mid)
      md1(pp, val, p << 1);
    else
      md1(pp, val, p << 1 | 1);
    v[p] = max(v[p << 1], v[p << 1 | 1]);
  }
  void md2(int l, int r, int p = 1) {
    if (ll[p] > r || rr[p] < l) return;
    if (l <= ll[p] && rr[p] <= r) {
      d[p]++;
      v[p]++;
      return;
    }
    pushdown(p);
    md2(l, r, p << 1);
    md2(l, r, p << 1 | 1);
    v[p] = max(v[p << 1], v[p << 1 | 1]);
  }
} seg;
int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  for (int i = 1; i <= n; i++) {
    siz[i] = 1;
    gp[i] = i;
  }
  set<pair<int, int> > st;
  for (int i = 1; i <= n; i++) {
    auto rr = st.lower_bound({a[i], -INF});
    for (auto it = st.begin(); it != rr; it++) {
      siz[i] += siz[-it->second];
      mem[i].push_back(-it->second);
    }
    while (!st.empty() && st.begin()->first < a[i]) st.erase(st.begin());
    st.insert({a[i], -i});
  }
  int cntp = 0;
  for (auto it : st) {
    cntp += siz[-it.second];
    pos[-it.second] = cntp;
    go(-it.second, cntp - 1);
  }
  seg.bd(1, n);
  for (int i = 1; i <= k; i++) {
    seg.md1(pos[i], 0);
    seg.md2(1, pos[i]);
  }
  printf("%d ", seg.qy());
  for (int i = k + 1; i <= n; i++) {
    seg.md1(pos[i - k], -INF);
    seg.md1(pos[i], 0);
    seg.md2(1, pos[i]);
    printf("%d ", seg.qy());
  }
  puts("");
  return 0;
}
