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;
mt19937 rng(static_cast<unsigned int>(
    chrono::steady_clock::now().time_since_epoch().count()));
template <typename num_t>
inline void add_mod(num_t& a, const int& b, const int& m) {
  a = (a + b);
  if (a >= m) a -= m;
}
template <typename num_t>
inline bool update_max(num_t& a, const num_t& b) {
  return a < b ? a = b, true : false;
}
template <typename num_t>
inline bool update_min(num_t& a, const num_t& b) {
  return a > b ? a = b, true : false;
}
template <typename num_t>
num_t gcd(num_t lhs, num_t rhs) {
  return !lhs ? rhs : gcd(rhs % lhs, lhs);
}
template <typename num_t>
num_t pw(num_t n, num_t k, const num_t& mod) {
  if (k == -1) k = mod - 2;
  num_t res = 1;
  for (; k > 0; k >>= 1) {
    if (k & 1) res = 1ll * res * n % mod;
    n = 1ll * n * n % mod;
  }
  return res % mod;
}
const int inf = 1e9 + 7;
const int mod = 998244353;
const long long ll_inf = 9ll * inf * inf + 7;
const int MAX_N = 5000 + 7;
template <typename num_t>
class SegmentTree {
 public:
  void init(int l, int r) {
    tree.resize((r - l + 1) << 1);
    node_index = 0;
    build_tree(tree[node_index++], l, r);
  }
  void update(int left_index, int right_index, const num_t& val) {
    update_(tree[0], left_index, right_index, val);
  }
  num_t get(int left_index, int right_index) {
    if (right_index < left_index) return 0;
    return get(tree[0], left_index, right_index);
  }

 private:
  struct node {
    static const num_t nil = 0;
    node *left_child, *right_child;
    int left_index, right_index;
    num_t value;
    num_t lazy;
    inline void push_down(num_t updated_value) {
      value += updated_value;
      lazy += updated_value;
    }
    inline void merge_node() {
      const node &lhs = *left_child, &rhs = *right_child;
      value = max(lhs.value, rhs.value);
    }
    inline void lazy_update() {
      if (lazy) {
        if (left_child != nullptr) left_child->push_down(lazy);
        if (right_child != nullptr) right_child->push_down(lazy);
        lazy = 0;
      }
    }
    inline void init_value(num_t v = 0) {
      value = v;
      lazy = 0;
    }
    inline void init(int left, int right, node* left_child_,
                     node* right_child_) {
      left_index = left;
      right_index = right;
      left_child = left_child_;
      right_child = right_child_;
    }
    int size() const { return right_index - left_index + 1; }
  };
  vector<node> tree;
  int node_index = 0;
  void build_tree(node& root, int left, int right) {
    if (left == right) {
      root.init(left, right, nullptr, nullptr);
      root.init_value(0);
      return;
    }
    int mid = (left + right) >> 1, lhs = node_index++, rhs = node_index++;
    build_tree(tree[lhs], left, mid);
    build_tree(tree[rhs], mid + 1, right);
    root.init(left, right, &tree[lhs], &tree[rhs]);
    root.init_value();
    root.merge_node();
  }
  void update_(node& root, int u, int v, const num_t& value) {
    if (u > root.right_index || v < root.left_index) return;
    if (u <= root.left_index && root.right_index <= v) {
      root.push_down(value);
    } else {
      root.lazy_update();
      update_(*root.left_child, u, v, value);
      update_(*root.right_child, u, v, value);
      root.init_value(0);
      root.merge_node();
    }
  }
  num_t get(node& root, int u, int v) {
    if (u <= root.left_index && root.right_index <= v) return root.value;
    if (u > root.right_index || v < root.left_index) return node::nil;
    root.lazy_update();
    auto lhs = get(*root.left_child, u, v);
    auto rhs = get(*root.right_child, u, v);
    return max(lhs, rhs);
  }
};
SegmentTree<int> tree;
int n, k;
vector<int> a;
void solve() {
  cin >> n >> k;
  a.resize(n);
  for (int& x : a) cin >> x;
  tree.init(0, n - 1);
  vector<int> stack_;
  for (int i = 0; i < n; ++i) {
    while (!stack_.empty() && a[stack_.back()] < a[i]) stack_.pop_back();
    int last = 0;
    if (!stack_.empty()) last = stack_.back() + 1;
    stack_.push_back(i);
    tree.update(last, i, 1);
    if (i + 1 >= k) cout << tree.get(i - k + 1, i) << ' ';
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  const bool multiple_test = false;
  int test = 1;
  if (multiple_test) cin >> test;
  for (int i = 0; i < test; ++i) {
    solve();
  }
}
