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>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
using namespace std;
vector<vector<long long> > g;
vector<long long> tin, tout;
long long timer = 0;
void dfs(long long v) {
  tin[v] = timer++;
  for (auto i : g[v]) {
    dfs(i);
  }
  tout[v] = timer - 1;
}
struct Node {
  long long mx, add;
};
vector<Node> tree;
void push(long long v) {
  if (tree[v].add != 0) {
    tree[v * 2 + 1].add += tree[v].add;
    tree[v * 2 + 1].mx += tree[v].add;
    tree[v * 2 + 2].add += tree[v].add;
    tree[v * 2 + 2].mx += tree[v].add;
    tree[v].add = 0;
  }
}
void addVal(long long v, long long tl, long long tr, long long l, long long r,
            long long val) {
  if (l > r) return;
  if (tl == l && tr == r) {
    tree[v].add += val;
    tree[v].mx += val;
    return;
  }
  long long tm = (tl + tr) / 2;
  push(v);
  addVal(v * 2 + 1, tl, tm, l, min(tm, r), val);
  addVal(v * 2 + 2, tm + 1, tr, max(tm + 1, l), r, val);
  tree[v].mx = max(tree[v * 2 + 1].mx, tree[v * 2 + 2].mx);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long n, k;
  cin >> n >> k;
  g.resize(n + 1);
  vector<long long> a(n);
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
  }
  tin.resize(n + 2), tout.resize(n + 2);
  stack<long long> st;
  for (int i = n - 1; i >= 0; i--) {
    while (!st.empty() && a[st.top()] <= a[i]) {
      st.pop();
    }
    long long nxt = st.empty() ? n : st.top();
    g[nxt].push_back(i);
    st.push(i);
  }
  dfs(n);
  tree.resize(4 * (n + 1), Node({0, 0}));
  for (long long i = 0; i < k - 1; i++) {
    addVal(0, 0, n + 1, tin[i], tout[i], 1);
    if (0) {
      cout << i << " " << tin[i] << " " << tout[i] << " " << 1 << "\n";
    }
  }
  for (long long l = 0; l + k <= n; l++) {
    addVal(0, 0, n + 1, tin[l + k - 1], tout[l + k - 1], +1);
    cout << tree[0].mx << " ";
    addVal(0, 0, n + 1, tin[l], tout[l], -1);
    if (0) {
      cout << l + k - 1 << " " << tin[l + k - 1] << " " << tout[l + k - 1]
           << " " << 1 << "\n";
      ;
      cout << l << " " << tin[l] << " " << tout[l] << " " << -1 << "\n";
    }
  }
  return 0;
}
