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 long long INF = 1e18 + 10;
const int SZ = 1e6 + 10;
const int mod = 1e9 + 7;
const double PI = acos(-1);
const double eps = 1e-7;
long long read() {
  long long n = 0;
  char a = getchar();
  bool flag = 0;
  while (a > '9' || a < '0') {
    if (a == '-') flag = 1;
    a = getchar();
  }
  while (a <= '9' && a >= '0') {
    n = n * 10 + a - '0', a = getchar();
  }
  if (flag) n = -n;
  return n;
}
int n, k, a[SZ];
vector<int> g[SZ];
void build_graph() {
  stack<int> S;
  for (int i = n; i >= 1; i--) {
    while (S.size() && a[S.top()] <= a[i]) S.pop();
    if (S.size()) g[S.top()].push_back(i);
    S.push(i);
  }
}
struct seg {
  int l, r;
  int add, maxn;
} tree[SZ * 4];
void update(int p) {
  tree[p].maxn = max(tree[p << 1].maxn, tree[p << 1 | 1].maxn);
}
void build(int p, int l, int r) {
  tree[p].l = l;
  tree[p].r = r;
  if (l == r) return;
  int mid = l + r >> 1;
  build(p << 1, l, mid);
  build(p << 1 | 1, mid + 1, r);
}
void pushadd(int p, int d) {
  tree[p].add += d;
  tree[p].maxn += d;
}
void pushdown(int p) {
  if (tree[p].add) {
    pushadd(p << 1, tree[p].add);
    pushadd(p << 1 | 1, tree[p].add);
    tree[p].add = 0;
  }
}
void change(int p, int l, int r, int d) {
  if (l <= tree[p].l && tree[p].r <= r) {
    pushadd(p, d);
    return;
  }
  pushdown(p);
  int mid = tree[p].l + tree[p].r >> 1;
  if (l <= mid) change(p << 1, l, r, d);
  if (mid < r) change(p << 1 | 1, l, r, d);
  update(p);
}
int dfn[SZ], sz[SZ], dfs_clock;
void dfs(int u) {
  dfn[u] = ++dfs_clock;
  sz[u] = 1;
  for (int v : g[u]) {
    dfs(v);
    sz[u] += sz[v];
  }
}
int main() {
  n = read(), k = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  build_graph();
  for (int i = n; i >= 1; i--)
    if (!dfn[i]) dfs(i);
  build(1, 1, n);
  for (int i = 1; i <= k; i++) change(1, dfn[i], dfn[i] + sz[i] - 1, 1);
  for (int i = k; i <= n; i++) {
    printf("%d ", tree[1].maxn);
    if (i < n) change(1, dfn[i + 1], dfn[i + 1] + sz[i + 1] - 1, 1);
    change(1, dfn[i - k + 1], dfn[i - k + 1] + sz[i - k + 1] - 1, -1);
  }
}
