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 maxn = 1e6 + 10;
int n, k, a[maxn];
vector<int> g[maxn];
int par[maxn], h[maxn];
void dfs(int cur) {
  for (auto nxt : g[cur]) {
    h[nxt] = h[cur] + 1;
    dfs(nxt);
  }
}
int p[maxn];
multiset<int> res[maxn];
multiset<int> ans;
int pa(int x) { return x == p[x] ? x : p[x] = pa(p[x]); }
inline int cal_ans(int id) {
  if (res[id].empty()) return 0;
  return *res[id].rbegin() - *res[id].begin() + 1;
}
inline void remove(int id) {
  int tmp = cal_ans(id);
  if (tmp) {
    ans.erase(ans.find(tmp));
  }
}
inline void add(int id) {
  int tmp = cal_ans(id);
  if (tmp) {
    ans.insert(tmp);
  }
}
void merge(int x, int y) {
  x = pa(x), y = pa(y);
  if (x != y) {
    if (res[x].size() < res[y].size()) swap(x, y);
    remove(x);
    remove(y);
    p[y] = x;
    for (const auto& e : res[y]) res[x].insert(e);
    res[y].clear();
    add(x);
  }
}
int main() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  int root = n + 1;
  a[root] = root;
  stack<int> stk;
  for (int i = 1; i <= root; ++i) {
    while (!stk.empty() && a[stk.top()] < a[i]) {
      g[i].push_back(stk.top());
      par[stk.top()] = i;
      stk.pop();
    }
    stk.push(i);
  }
  assert(stk.size() == 1 && stk.top() == root);
  h[root] = 0;
  dfs(root);
  for (int i = 1; i <= root; ++i) p[i] = i;
  for (int i = 1; i <= k; ++i) {
    res[i].insert(h[i]);
    ans.insert(1);
    for (auto child : g[i]) merge(i, child);
  }
  printf("%d", *ans.rbegin());
  for (int i = k + 1; i <= n; ++i) {
    res[i].insert(h[i]);
    ans.insert(1);
    for (auto child : g[i]) merge(i, child);
    int tmp = pa(i - k);
    remove(tmp);
    res[tmp].erase(res[tmp].find(h[i - k]));
    add(tmp);
    printf(" %d", *ans.rbegin());
  }
  puts("");
}
