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 <class T, class T2>
inline bool chkmax(T &x, const T2 &y) {
  return x < y ? x = y, 1 : 0;
}
template <class T, class T2>
inline bool chkmin(T &x, const T2 &y) {
  return x > y ? x = y, 1 : 0;
}
const long long mod = 1e9 + 7;
template <class T>
inline void fix(T &x) {
  if (x >= mod | x <= -mod) {
    x %= mod;
  }
  if (x < 0) {
    x += mod;
  }
}
const long long MAX_N = 1e6 + 10;
struct SegTree {
  long long tree[4 * MAX_N], lazy[4 * MAX_N];
  SegTree() {
    fill_n(tree, 4 * MAX_N, 0);
    fill_n(lazy, 4 * MAX_N, 0);
  }
  void push(long long curr, long long l, long long r) {
    tree[curr] += lazy[curr];
    if (l != r) {
      lazy[curr * 2] += lazy[curr];
      lazy[curr * 2 + 1] += lazy[curr];
    }
    lazy[curr] = 0;
  }
  void upd(long long curr, long long l, long long r, long long ql, long long qr,
           long long val) {
    push(curr, l, r);
    if (ql <= l && r <= qr) {
      lazy[curr] += val;
      push(curr, l, r);
      return;
    } else if (l > qr || r < ql) {
      return;
    }
    long long m = (l + r) / 2;
    upd(curr * 2, l, m, ql, qr, val);
    upd(curr * 2 + 1, m + 1, r, ql, qr, val);
    tree[curr] = max(tree[curr * 2], tree[curr * 2 + 1]);
  }
  long long ans(long long curr, long long l, long long r) {
    push(curr, l, r);
    return tree[curr];
  }
};
vector<long long> g[MAX_N];
long long in[MAX_N], out[MAX_N], tme = 0;
long long n, k;
long long arr[MAX_N];
void dfs(long long x) {
  in[x] = ++tme;
  for (auto it : g[x]) {
    dfs(it);
  }
  out[x] = tme;
}
SegTree str;
void add(long long x) { str.upd(1, 0, tme + 1, in[x], out[x], 1); }
void remove(long long x) { str.upd(1, 0, tme + 1, in[x], in[x], -mod * mod); }
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> k;
  for (long long i = 0; i < n; i++) {
    cin >> arr[i];
  }
  stack<long long> st;
  st.push(n);
  arr[n] = mod;
  for (long long i = n - 1; i >= 0; i--) {
    while (arr[i] >= arr[st.top()]) {
      st.pop();
    }
    g[st.top()].push_back(i);
    st.push(i);
  }
  dfs(n);
  for (long long i = 0; i < k; i++) {
    add(i);
  }
  for (long long i = 0; i + k < n; i++) {
    cout << str.ans(1, 0, tme + 1) << " ";
    remove(i);
    add(i + k);
  }
  cout << str.ans(1, 0, tme) << "\n";
  return 0;
}
