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;
const int N = 1000004;
int t[4 * N];
int d[4 * N];
void upd(int v, int x) {
  t[v] += x;
  d[v] += x;
}
void push(int v) {
  if (d[v]) {
    upd(2 * v + 1, d[v]);
    upd(2 * v + 2, d[v]);
    d[v] = 0;
  }
}
void upd(int v, int l, int r, int x, int tl = 0, int tr = N) {
  if (r <= tl || tr <= l) {
    return;
  } else if (l <= tl && tr <= r) {
    upd(v, x);
  } else {
    push(v);
    int tm = (tl + tr) / 2;
    upd(2 * v + 1, l, r, x, tl, tm);
    upd(2 * v + 2, l, r, x, tm, tr);
    t[v] = max(t[2 * v + 1], t[2 * v + 2]);
  }
}
int get(int v, int l, int r, int tl = 0, int tr = N) {
  if (r <= tl || tr <= l) {
    return 0;
  } else if (l <= tl && tr <= r) {
    return t[v];
  } else {
    push(v);
    int tm = (tl + tr) / 2;
    return max(get(2 * v + 1, l, r, tl, tm), get(2 * v + 2, l, r, tm, tr));
  }
}
vector<int> g[N];
int tin[N];
int tout[N];
int timer;
void dfs(int v, int p = -1) {
  tin[v] = timer++;
  for (int to : g[v]) {
    if (to != p) {
      dfs(to, v);
    }
  }
  tout[v] = timer;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<int> R(n);
  for (int i = n - 1; i >= 0; i--) {
    R[i] = i + 1;
    while (R[i] < n && a[i] >= a[R[i]]) {
      R[i] = R[R[i]];
    }
    g[R[i]].push_back(i);
  }
  dfs(n);
  int j = 0;
  for (int i = 0; i + k <= n; i++) {
    while (j < i + k) {
      upd(0, tin[j], tout[j], 1);
      ++j;
    }
    cout << get(0, 0, N) << ' ';
    upd(0, tin[i], tin[i] + 1, -N);
  }
  cout << '\n';
  return 0;
}
