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 <typename A, typename B>
ostream &operator<<(ostream &cout, pair<A, B> const &p) {
  return cout << "(" << p.first << ", " << p.second << ")";
}
template <typename A>
ostream &operator<<(ostream &cout, vector<A> const &v) {
  cout << "[";
  for (int i = 0; i < v.size(); i++) {
    if (i) cout << ", ";
    cout << v[i];
  }
  return cout << "]";
}
int t, n, k, itr[8000005], lz[8000005], a[1000005], cmp, par[1000005],
    tin[1000005], tout[1000005];
int sz;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>
    ndpar;
vector<int> e[1000005];
void psh(int z, int l, int r) {
  itr[z] += lz[z];
  if (l != r) {
    lz[2 * z] += lz[z];
    lz[2 * z + 1] += lz[z];
  }
  lz[z] = 0;
}
void iupd(int z, int l, int r, int lb, int rb, int b) {
  psh(z, l, r);
  if (r < lb || l > rb) return;
  if (l >= lb && r <= rb) {
    lz[z] += b;
    psh(z, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  iupd(2 * z, l, mid, lb, rb, b);
  iupd(2 * z + 1, mid + 1, r, lb, rb, b);
  itr[z] = max(itr[2 * z + 1], itr[2 * z]);
}
void upd(int l, int r, int b) { iupd(1, 1, sz, l, r, b); }
int ige(int z, int l, int r, int lb, int rb) {
  psh(z, l, r);
  if (r < lb || l > rb) return 0;
  if (l >= lb && r <= rb) return itr[z];
  int mid = (l + r) >> 1;
  return max(ige(2 * z, l, mid, lb, rb), ige(2 * z + 1, mid + 1, r, lb, rb));
}
int ge(int l, int r) { return ige(1, 1, sz, l, r); }
void dfs(int g) {
  sz++;
  tin[g] = sz;
  for (auto u : e[g]) dfs(u);
  sz++;
  tout[g] = sz;
}
void solve() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> a[i];
  cmp = 1;
  for (int i = 1; i <= n; i++) {
    while (!ndpar.empty() && ndpar.top().first < a[i]) {
      par[ndpar.top().second] = i;
      ndpar.pop();
    }
    ndpar.push({a[i], i});
  }
  sz = 0;
  for (int i = 1; i <= n; i++) {
    e[par[i]].push_back(i);
  }
  dfs(0);
  for (int i = 1; i <= k; i++) upd(tin[i], tout[i], 1);
  cout << ge(1, sz) << ' ';
  for (int st = 2; st + k - 1 <= n; st++) {
    upd(tin[st - 1], tout[st - 1], -1);
    upd(tin[st + k - 1], tout[st + k - 1], 1);
    cout << ge(1, sz) << ' ';
  }
  cout << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  t = 1;
  for (int i = 1; i <= t; i++) solve();
  cout.flush();
  return 0;
}
