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>
inline void chmin(A &a, B b) {
  if (a > b) a = b;
}
template <typename A, typename B>
inline void chmax(A &a, B b) {
  if (a < b) a = b;
}
template <class W, long long lg = 1>
struct WeightedTree {
  struct Edge {
    long long to;
    W cost;
    Edge(long long to, W cost) : to(to), cost(cost) {}
  };
  long long V;
  long long root;
  vector<vector<Edge>> G;
  vector<vector<long long>> par;
  vector<long long> dep, sz, head;
  vector<long long> tin, tout;
  vector<W> dist;
  WeightedTree(long long V = 0, long long root = 0)
      : V(V),
        root(root),
        G(V),
        par(lg, vector<long long>(V)),
        sz(V),
        dep(V),
        head(V),
        dist(V),
        tin(V),
        tout(V) {}
  void addEdge(long long a, long long b, W c = W(1)) {
    G[a].push_back(Edge(b, c));
    G[b].push_back(Edge(a, c));
  }
  void dfs(long long v, long long p, long long d, W c) {
    par[0][v] = p;
    dep[v] = d;
    sz[v] = 1;
    dist[v] = c;
    for (auto &e : G[v]) {
      if (e.to == p) continue;
      dfs(e.to, v, d + 1, c + e.cost);
      sz[v] += sz[e.to];
      if (G[v][0].to == p || sz[e.to] > sz[G[v][0].to]) swap(G[v][0], e);
    }
  }
  void dfs_hld(long long v, long long &tt) {
    tin[v] = tt++;
    for (auto &e : G[v]) {
      if (e.to == par[0][v]) continue;
      head[e.to] = (e.to == G[v][0].to) ? head[v] : e.to;
      dfs_hld(e.to, tt);
    }
    tout[v] = tt;
  }
  void init() {
    dfs(root, -1, 0, W(0));
    long long tt = 0;
    dfs_hld(root, tt);
    for (long long i = 0; i + 1 < lg; i++) {
      for (long long j = 0; j < V; j++) {
        if (par[i][j] == -1)
          par[i + 1][j] = -1;
        else
          par[i + 1][j] = par[i][par[i][j]];
      }
    }
  }
  long long getLCA(long long u, long long v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (long long i = 0; i < (lg); i++)
      if ((dep[u] - dep[v]) >> i & 1) u = par[i][u];
    if (u == v) return u;
    for (long long i = lg - 1; i >= 0; i--)
      if (par[i][u] != par[i][v]) u = par[i][u], v = par[i][v];
    return par[0][v];
  }
  long long getLength(long long a, long long b = 0) {
    long long l = getLCA(a, b);
    return dep[a] + dep[b] - 2 * dep[l];
  }
  W getDistance(long long a, long long b = 0) {
    long long l = getLCA(a, b);
    return dist[a] + dist[b] - 2 * dist[l];
  }
  long long getParent(long long v, long long k = 0) { return par[k][v]; }
  long long getDepth(long long v) { return dep[v]; }
  long long getIn(long long v) { return tin[v]; }
  long long getOut(long long v) { return tout[v]; }
};
WeightedTree<long long> T;
const long long SEG = 1 << 20;
long long dat[SEG * 2], put[SEG * 2];
void add(long long a, long long b, long long x, long long k = 0,
         long long l = 0, long long r = SEG) {
  if (r <= a || b <= l) return;
  if (a <= l && r <= b) {
    put[k] += x;
    return;
  }
  add(a, b, x, k * 2 + 1, l, (l + r) / 2);
  add(a, b, x, k * 2 + 2, (l + r) / 2, r);
  dat[k] =
      max(dat[k * 2 + 1] + put[k * 2 + 1], dat[k * 2 + 2] + put[k * 2 + 2]);
}
long long query(long long a, long long b, long long k = 0, long long l = 0,
                long long r = SEG) {
  if (r <= a || b <= l) return 0;
  if (a <= l && r <= b) return dat[k] + put[k];
  return max(query(a, b, k * 2 + 1, l, (l + r) / 2),
             query(a, b, k * 2 + 2, (l + r) / 2, r)) +
         put[k];
}
signed main() {
  long long N, K;
  scanf("%lld%lld", &N, &K);
  vector<long long> A(N);
  for (long long i = 0; i < (N); i++) scanf("%lld", &A[i]);
  T = WeightedTree<long long>(N + 1, N);
  vector<long long> stk;
  for (long long i = N - 1; i >= 0; i--) {
    while (stk.size() && A[stk.back()] <= A[i]) stk.pop_back();
    if (stk.size()) {
      T.addEdge(i, stk.back());
    } else {
      T.addEdge(N, i);
    }
    stk.push_back(i);
  }
  long long sum = 0;
  for (long long i = 0; i < (N + 1); i++) sum += T.G[i].size();
  T.init();
  for (long long i = 0; i < (K - 1); i++) {
    add(T.getIn(i), T.getOut(i), 1);
  }
  for (long long i = 0; i + K <= N; i++) {
    add(T.getIn(i + K - 1), T.getOut(i + K - 1), 1);
    if (i) printf(" ");
    printf("%lld", query(T.getIn(N), T.getOut(N)));
    add(T.getIn(i), T.getOut(i), -1);
  }
  return 0;
}
