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 INF = 1e6 + 5;
int N, K, A[INF], Id[INF], Size[INF], F[4 * INF], mrk[4 * INF], l = 1, cnt, ans;
stack<pair<int, int> > S;
vector<int> V[INF];
void dfs(int n) {
  Id[n] = ++cnt;
  Size[n] = 1;
  for (int i = 0, zj; i < V[n].size(); i++) {
    zj = V[n][i];
    dfs(zj);
    Size[n] += Size[zj];
  }
}
void pu(int O) {
  F[O * 2] += mrk[O];
  F[O * 2 + 1] += mrk[O];
  mrk[O * 2] += mrk[O];
  mrk[O * 2 + 1] += mrk[O];
  mrk[O] = 0;
}
void add(int O, int l, int r, int s, int t) {
  if (l == s && r == t) {
    F[O]++;
    mrk[O]++;
    return;
  }
  if (mrk[O]) pu(O);
  int mid = (l + r) / 2;
  if (t <= mid)
    add(O * 2, l, mid, s, t);
  else if (s > mid)
    add(O * 2 + 1, mid + 1, r, s, t);
  else {
    add(O * 2, l, mid, s, mid);
    add(O * 2 + 1, mid + 1, r, mid + 1, t);
  }
  F[O] = max(F[O * 2], F[O * 2 + 1]);
}
void del(int O, int l, int r, int s, int t) {
  if (l == s && r == t) {
    F[O]--;
    mrk[O]--;
    return;
  }
  if (mrk[O]) pu(O);
  int mid = (l + r) / 2;
  if (t <= mid)
    del(O * 2, l, mid, s, t);
  else if (s > mid)
    del(O * 2 + 1, mid + 1, r, s, t);
  else {
    del(O * 2, l, mid, s, mid);
    del(O * 2 + 1, mid + 1, r, mid + 1, t);
  }
  F[O] = max(F[O * 2], F[O * 2 + 1]);
}
int qu(int O, int l, int r, int s, int t) {
  if (l == s && r == t) return F[O];
  if (mrk[O]) pu(O);
  int mid = (l + r) / 2;
  if (t <= mid)
    return qu(O * 2, l, mid, s, t);
  else if (s > mid)
    return qu(O * 2 + 1, mid + 1, r, s, t);
  else
    return max(qu(O * 2, l, mid, s, mid),
               qu(O * 2 + 1, mid + 1, r, mid + 1, t));
}
int main() {
  scanf("%d %d", &N, &K);
  for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
  for (int i = 1; i <= N; i++) {
    while (!S.empty() && S.top().first < A[i]) {
      V[i].push_back(S.top().second);
      S.pop();
    }
    S.push(make_pair(A[i], i));
  }
  while (!S.empty()) {
    V[N + 1].push_back(S.top().second);
    S.pop();
  }
  dfs(N + 1);
  for (int i = 1; i <= K; i++) add(1, 1, N + 1, Id[i], Id[i] + Size[i] - 1);
  ans = qu(1, 1, N + 1, 1, N + 1);
  printf("%d ", ans);
  for (int i = K + 1; i <= N; i++) {
    add(1, 1, N + 1, Id[i], Id[i] + Size[i] - 1);
    if (i - l + 1 > K) {
      del(1, 1, N + 1, Id[l], Id[l] + Size[l] - 1);
      l++;
    }
    ans = qu(1, 1, N + 1, 1, N + 1);
    printf("%d ", ans);
  }
  return 0;
}
