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;
enum seg_type { seg_not_lazy, seg_lazy, seg_beats };
template <class node, seg_type type>
struct segment_tree {
  using node_container = typename node::node_container;
  using lazy_container = typename node::lazy_container;

 private:
  template <const bool T = (type != seg_not_lazy),
            typename enable_if<T, bool>::type = 0>
  inline void push(int x, int b, int e, int m) {
    if (st[x].lazy()) {
      st[x + 1].apply(b, m, st[x].lazy);
      st[x + ((m - b) << 1)].apply(m, e, st[x].lazy);
      st[x].lazy = lazy_container();
    }
  }
  template <const bool T = (type != seg_not_lazy),
            typename enable_if<!T, bool>::type = 0>
  inline void push(int x, int b, int e, int m) {}
  template <typename RAIter>
  void build(int x, int b, int e, const RAIter &a) {
    if (b + 1 == e) {
      st[x].nod.build(a[b]);
      return;
    }
    int m = (b + e) >> 1;
    int y = x + ((m - b) << 1);
    build(x + 1, b, m, a);
    build(y, m, e, a);
    st[x].nod = st[x + 1].nod + st[y].nod;
  }
  template <const bool T = (type == seg_beats),
            typename enable_if<!T, bool>::type = 0>
  void update_(int x, int b, int e) {
    if (lo <= b && e <= hi) {
      st[x].apply(b, e, lazy);
      return;
    }
    int m = (b + e) >> 1;
    int y = x + ((m - b) << 1);
    push(x, b, e, m);
    if (lo < m) update_(x + 1, b, m);
    if (m < hi) update_(y, m, e);
    st[x].nod = st[x + 1].nod + st[y].nod;
  }
  template <const bool T = (type == seg_beats),
            typename enable_if<T, bool>::type = 0>
  void update_(int x, int b, int e) {
    if (st[x].break_condition(lazy)) return;
    if (lo <= b && e <= hi && st[x].tag_condition(lazy)) {
      st[x].apply(b, e, lazy);
      return;
    }
    int m = (b + e) >> 1;
    int y = x + ((m - b) << 1);
    push(x, b, e, m);
    if (lo < m) update_(x + 1, b, m);
    if (m < hi) update_(y, m, e);
    st[x].nod = st[x + 1].nod + st[y].nod;
  }
  node_container query(int x, int b, int e) {
    if (lo <= b && e <= hi) return st[x].nod;
    int m = (b + e) >> 1;
    int y = x + ((m - b) << 1);
    push(x, b, e, m);
    if (m >= hi) return query(x + 1, b, m);
    if (m <= lo) return query(y, m, e);
    return query(x + 1, b, m) + query(y, m, e);
  }
  template <class P>
  int find_first(int x, int b, int e, const P &f) {
    if (b + 1 == e) return f(st[x]) ? b : -1;
    int m = (b + e) >> 1;
    int y = x + ((m - b) << 1);
    push(x, b, e, m);
    if (lo < m && f(st[x + 1])) {
      auto t = find_first(x + 1, b, m, f);
      if (t != -1) return t;
    }
    if (m < hi && f(st[y])) return find_first(y, m, e, f);
    return -1;
  }
  template <class P>
  int find_last(int x, int b, int e, const P &f) {
    if (b + 1 == e) return f(st[x]) ? b : -1;
    int m = (b + e) >> 1;
    int y = x + ((m - b) << 1);
    push(x, b, e, m);
    if (m < hi && f(st[y])) {
      auto t = find_last(y, m, e, f);
      if (t != -1) return t;
    }
    if (lo < m && f(st[x + 1])) return find_last(x + 1, b, m, f);
    return -1;
  }
  lazy_container lazy;
  int n, lo, hi;
  vector<node> st;

 public:
  template <typename RAIter>
  void build(const RAIter &a) {
    build(0, 0, n, a);
  }
  void update(int l, int r, const lazy_container &x) {
    lo = l, hi = r, lazy = x, update_(0, 0, n);
  }
  node_container query(int l, int r) { return lo = l, hi = r, query(0, 0, n); }
  template <class P>
  int find_first(int l, int r, const P &f) {
    return lo = l, hi = r, find_first(0, 0, n, f);
  }
  template <class P>
  int find_last(int l, int r, const P &f) {
    return lo = l, hi = r, find_last(0, 0, n, f);
  }
  segment_tree(int n) : n(n), st(2 * n - 1) {}
};
struct node {
  struct node_container {
    int x;
    friend node_container operator+(node_container l, const node_container &r) {
      l.x = max(l.x, r.x);
      return l;
    }
    node_container() : x(-1e9) {}
  } nod;
  struct lazy_container {
    int s;
    inline bool operator()() { return s != 0; }
    lazy_container(int s = 0) : s(s) {}
  } lazy;
  inline void apply(int l, int r, lazy_container &p) {
    nod.x += p.s;
    lazy.s += p.s;
  }
};
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (auto &i : a) cin >> i;
  a.push_back(1e9);
  vector<int> stk = {n};
  vector<vector<int>> adj(n + 1);
  for (int i = n - 1; i >= 0; --i) {
    while (a[i] >= a[stk.back()]) stk.pop_back();
    adj[stk.back()].push_back(i);
    stk.push_back(i);
  }
  int id = 0;
  vector<int> dt(n + 1), ft(n + 1);
  function<void(int)> dfs = [&](int u) {
    dt[u] = id++;
    for (auto v : adj[u]) dfs(v);
    ft[u] = id;
  };
  dfs(n);
  segment_tree<node, seg_lazy> st(n + 1);
  auto upsub = [&](int u) {
    st.update(dt[u], dt[u] + 1, -st.query(dt[u], dt[u] + 1).x);
    st.update(dt[u], ft[u], +1);
  };
  for (int i = 0; i < k; ++i) upsub(i);
  for (int i = k; i <= n; ++i) {
    cout << st.query(0, n + 1).x << " \n"[i == n];
    upsub(i);
    st.update(dt[i - k], dt[i - k] + 1, -1e9);
  }
  return 0;
}
