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 n, k;
vector<int> a, bit;
bool par[1000005];
vector<int> in, out;
int cnt(0);
struct it {
  int COUNT, LAZY;
  it *l, *r;
  void Update(int l, int r, int L, int R, int a);
};
it *add() {
  it *t = new it;
  t->COUNT = 0;
  t->LAZY = 0;
  t->l = t->r = NULL;
  return t;
}
void it::Update(int l, int r, int L, int R, int a) {
  if (r < L || R < l) return;
  if (L <= l && r <= R) {
    this->COUNT += a;
    this->LAZY += a;
    return;
  }
  if (this->r == NULL) this->r = add();
  if (this->l == NULL) this->l = add();
  if (this->LAZY) {
    this->l->COUNT += this->LAZY;
    this->r->COUNT += this->LAZY;
    this->l->LAZY += this->LAZY;
    this->r->LAZY += this->LAZY;
    this->LAZY = 0;
  }
  int m = (l + r) / 2;
  this->l->Update(l, m, L, R, a);
  this->r->Update(m + 1, r, L, R, a);
  this->COUNT = max(this->l->COUNT, this->r->COUNT);
}
it *root;
vector<vector<int> > P;
template <class T>
T MAX(T a, T b) {
  return (a > b) ? a : b;
};
template <class T>
T MIN(T a, T b) {
  return (a < b) ? a : b;
};
int GetBit(int u) {
  int dapan = 1e9;
  for (int i = n - u + 1; i >= 1; i -= i & (-i)) {
    if (bit[i]) dapan = MIN(dapan, bit[i]);
  }
  return dapan;
}
void Update(int u, int v) {
  for (int i = n - u + 1; i <= n; i += i & (-i)) {
    if (bit[i])
      bit[i] = MIN(bit[i], v);
    else
      bit[i] = v;
  }
}
void Dfs(int u) {
  in[u] = ++cnt;
  for (int v : P[u]) {
    Dfs(v);
  }
  out[u] = cnt;
}
int main() {
  scanf("%d%d", &n, &k);
  P.resize(n + 3);
  a.resize(n + 3);
  in.resize(n + 3);
  out.resize(n + 3);
  bit.resize(n + 3);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = n; i >= 1; i--) {
    int x = GetBit(a[i] + 1);
    if (x != 1e9) {
      P[x].push_back(i);
      par[i] = 1;
    }
    Update(a[i], i);
  }
  for (int i = 1; i <= n; i++) {
    if (!par[i]) {
      P[n + 1].push_back(i);
    }
  }
  Dfs(n + 1);
  root = add();
  for (int i = 1; i < k; i++) {
    root->Update(1, cnt, in[i], out[i], 1);
  }
  for (int i = k; i <= n; i += 1) {
    root->Update(1, cnt, in[i], out[i], 1);
    printf("%d ", root->COUNT);
    root->Update(1, cnt, in[i - k + 1], out[i - k + 1], -1);
  }
}
