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 int mod = 1e9 + 7;
const int mod1 = 998244353;
#pragma GCC optimize("Ofast")
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
  uniform_int_distribution<int> uid(l, r);
  return uid(rng);
}
long long int pwr(long long int a, long long int b) {
  a %= mod;
  int ans = 1;
  while (b) {
    if (b & 1) ans = (ans * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return ans;
}
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << '\n'; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
class Segtree_With_lazy {
 public:
  vector<int> t, lz;
  int n, h;
  Segtree_With_lazy(int n) : n(n) {
    t.resize(2 * n, 0);
    lz.resize(n, 0);
    h = sizeof(int) * 8 - __builtin_clz(n);
    42;
  }
  void apply(int p, int val) {
    t[p] += val;
    if (p < n) lz[p] += val;
  }
  void build(int p) {
    while (p > 1) p >>= 1, t[p] = max(t[p << 1], t[p << 1 | 1]) + lz[p];
  }
  void push(int p) {
    for (int s = h; s > 0; s--) {
      int i = p >> s;
      if (lz[i]) {
        apply(i << 1, lz[i]);
        apply(i << 1 | 1, lz[i]);
        lz[i] = 0;
      }
    }
  }
  void inc(int l, int r, int val) {
    r++;
    l += n, r += n;
    int l0 = l, r0 = r;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) apply(l++, val);
      if (r & 1) apply(--r, val);
    }
    build(l0);
    build(r0 - 1);
  }
  int query(int l, int r) {
    r++;
    l += n, r += n;
    push(l);
    push(r - 1);
    int res = -2e9;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) res = max(res, t[l++]);
      if (r & 1) res = max(res, t[--r]);
    }
    return res;
  }
};
int tt = 0;
vector<int> s, e;
void dfs(int u, vector<vector<int>> &g) {
  s[u] = tt++;
  for (int v : g[u]) {
    dfs(v, g);
  }
  e[u] = tt - 1;
}
void solve() {
  int n, k;
  cin >> n >> k;
  42;
  vector<int> a(n);
  s.resize(n + 1), e.resize(n + 1);
  for (int i = 0; i <= n - 1; i++) {
    cin >> a[i];
  }
  stack<pair<int, int>> st;
  st.push({1e9 + 5, n});
  vector<vector<int>> g(n + 1);
  for (int i = n - 1; i >= 0; i--) {
    while (st.top().first <= a[i]) st.pop();
    g[st.top().second].push_back(i);
    st.push({a[i], i});
    42;
  }
  dfs(n, g);
  Segtree_With_lazy S(n + 1);
  for (int i = 0; i <= n - 1; i++) {
    S.inc(s[i], e[i], 1);
    42;
    if (i >= k) {
      S.inc(s[i - k], s[i - k], -1e9);
    }
    if (i >= k - 1) {
      cout << S.query(0, n) << " ";
    }
  }
}
signed main() {
  ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t = 1;
  for (int tt = 1; tt <= t; tt++) {
    solve();
  }
  return 0;
}
