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;
template <typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &a) {
  in >> a.first >> a.second;
  return in;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &out, pair<T1, T2> a) {
  out << a.first << " " << a.second;
  return out;
}
template <typename T, typename T1>
T maxs(T &a, T1 b) {
  if (b > a) a = b;
  return a;
}
template <typename T, typename T1>
T mins(T &a, T1 b) {
  if (b < a) a = b;
  return a;
}
const long long N = 1000005;
struct node {
  long long a = 0;
  node(long long val = 0) { a = val; }
  void merge(node &n1, node &n2) { this->a = max(n1.a, n2.a); }
};
struct update {
  long long val = 0;
  update(long long t = 0) { val = t; }
  void combine(update &par, long long tl, long long tr) { val += par.val; }
  void apply(node &node) {
    node.a += val;
    val = 0;
  }
};
template <typename node, typename update>
struct segtree {
  node t[4 * N];
  bool lazy[4 * N];
  update zaker[4 * N];
  long long tl[4 * N];
  long long tr[4 * N];
  node nul;
  inline void pushdown(long long v) {
    if (lazy[v]) {
      apply(zaker[v], v);
      lazy[v] = 0;
      zaker[v].apply(t[v]);
    }
  }
  inline void apply(update &u, long long v) {
    if (tl[v] != tr[v]) {
      lazy[2 * v] = lazy[2 * v + 1] = 1;
      zaker[2 * v].combine(u, tl[2 * v], tr[2 * v]);
      zaker[2 * v + 1].combine(u, tl[2 * v + 1], tr[2 * v + 1]);
    }
  }
  void build(long long v, long long start, long long end) {
    tl[v] = start;
    tr[v] = end;
    if (start == end) {
      t[v].a = 0;
    } else {
      long long m = (start + end) / 2;
      build(2 * v, start, m);
      build(2 * v + 1, m + 1, end);
      t[v].merge(t[2 * v], t[2 * v + 1]);
    }
  }
  void zeno(long long v, long long l, long long r, update val) {
    pushdown(v);
    if (tr[v] < l || tl[v] > r) return;
    if (l <= tl[v] && tr[v] <= r) {
      t[v].a += val.val;
      apply(val, v);
      return;
    }
    zeno(2 * v, l, r, val);
    zeno(2 * v + 1, l, r, val);
    t[v].merge(t[2 * v], t[2 * v + 1]);
  }
  node query(long long v, long long l, long long r) {
    if (tr[v] < l || tl[v] > r) return nul;
    pushdown(v);
    if (l <= tl[v] && tr[v] <= r) {
      return t[v];
    }
    node a = query(2 * v, l, r);
    node b = query(2 * v + 1, l, r);
    node ans;
    ans.merge(a, b);
    return ans;
  }

 public:
  node query(long long l, long long r) { return query(1, l, r); }
  void upd(long long l, long long r, update val) { return zeno(1, l, r, val); }
};
segtree<node, update> seg;
vector<long long> g[N];
long long eu[N], tin[N], tout[N];
long long t = 0;
void dfs(long long u, long long p) {
  tin[u] = ++t;
  eu[t] = u;
  for (auto i : g[u]) {
    if (i != p) dfs(i, u);
  }
  tout[u] = t;
}
long long solve() {
  long long n, k;
  cin >> n >> k;
  vector<long long> a(n + 1);
  for (long long i = 1; i < n + 1; i++) {
    cin >> a[i];
  }
  vector<long long> nxt(n + 1);
  stack<pair<long long, long long> > st;
  for (long long i = 1; i <= n; i++) {
    while (!st.empty() && st.top().first < a[i]) {
      nxt[st.top().second] = i;
      st.pop();
    }
    st.push({a[i], i});
  }
  while (!st.empty()) {
    nxt[st.top().second] = n + 1;
    st.pop();
  }
  for (long long i = 1; i <= n; i++) {
    g[nxt[i]].push_back(i);
  }
  dfs(n + 1, 0);
  seg.build(1, 1, n + 1);
  update upd1, upd2;
  upd1.val = 1, upd2.val = -1;
  for (long long i = 1; i <= k; i++) seg.upd(tin[i], tout[i], upd1);
  cout << seg.query(1, n + 1).a << " ";
  for (long long i = 2; i + k - 1 <= n; i++) {
    seg.upd(tin[i - 1], tout[i - 1], upd2);
    seg.upd(tin[i + k - 1], tout[i + k - 1], upd1);
    cout << seg.query(1, n + 1).a << " ";
  }
  return 0;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
