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;
int const N = 1000000;
int x[N], pa[N], lc[N];
stack<int> st;
multiset<int> an;
set<pair<int, int> > tr[N];
int P(int v) { return pa[v] < 0 ? v : pa[v] = P(pa[v]); }
int sz(int id) {
  assert(!tr[id].empty());
  return tr[id].rbegin()->first - tr[id].begin()->first + 1;
}
void J(int a, int b) {
  int of = tr[a].rbegin()->first - tr[b].rbegin()->first - 1;
  if (tr[a].size() < tr[b].size()) {
    swap(tr[a], tr[b]);
    of = tr[a].rbegin()->first - tr[b].rbegin()->first + 1;
  }
  for (auto it = tr[b].begin(); it != tr[b].end(); tr[b].erase(it++)) {
    int id = it->second;
    lc[id] = it->first + of;
    tr[a].insert(make_pair(lc[id], id));
  }
  pa[b] = a;
}
void ad(int id) {
  tr[id].insert(make_pair(0, id));
  while (!st.empty() && x[st.top()] < x[id]) {
    if (!tr[st.top()].empty()) {
      an.erase(an.find(sz(st.top())));
      J(id, st.top());
    }
    st.pop();
  }
  st.push(id);
  an.insert(sz(id));
}
void er(int id) {
  int g = P(id);
  an.erase(an.find(sz(g)));
  tr[g].erase(make_pair(lc[id], id));
  if (!tr[g].empty()) an.insert(sz(g));
}
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 0; i < (int)(n); ++i) scanf("%d", x + i);
  for (int i = 0; i < (int)(n); ++i) pa[i] = -1;
  bool sp = false;
  for (int i = 0; i < (int)(n); ++i) {
    if (i - k >= 0) er(i - k);
    ad(i);
    if (i + 1 >= k) {
      if (sp)
        printf(" ");
      else
        sp = true;
      printf("%d", *an.rbegin());
    }
  }
  printf("\n");
}
