Problem: For a given array $a_1, a_2, a_3, ... , a_N$ of $N$ elements and an integer $L$, find the minimum of each possible sub-arrays with size $L$ and print them from the beginning. For example, for an array $\\{1, 7, 7, 4, 8, 1, 6\\}$ and $L = 3$, the possible sub-arrays with size $L = 3$ includes $\\{1, 7, 7\\}$, $\\{7, 7, 4\\}$, $\\{7, 4, 8\\}$, $\\{4, 8, 1\\}$, $\\{8, 1, 6\\}$ and the minimum of each sub-array is 1, 4, 4, 1, 1 respectively.

Constraints

* $1 \leq N \leq 10^6$
* $1 \leq L \leq 10^6$
* $1 \leq a_i \leq 10^9$
* $L \leq N$

Input

The input is given in the following format.

$N$ $L$
$a_1$ $a_2$ ... $a_N$

Output

Print a sequence of the minimum in a line. Print a space character between adjacent elements.

Example

Input

7 3
1 7 7 4 8 1 6


Output

1 4 4 1 1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
template <class Z> Z getint() {
  char c = getchar();
  bool neg = c == '-';
  Z res = neg ? 0 : c - '0';
  while (isdigit(c = getchar())) res = res * 10 + (c - '0');
  return neg ? -res : res;
}
template <class Z> void putint(Z a, char c = '\n') {
  if (a < 0) putchar('-'), a = -a;
  int d[40], i = 0;
  do d[i++] = a % 10; while (a /= 10);
  while (i--) putchar('0' + d[i]);
  putchar(c);
}

template <class T, T Op(T, T), T E()> struct FoldableDeque {
  vector<T> l, r, cuml{E()}, cumr{E()};
  T fold() const { return Op(cuml.back(), cumr.back()); }
  void build(vector<T> v) {
    l = r = {}, cuml = cumr = {E()};
    int n = v.size();
    for (int i = n / 2; i != n; ++i) push_back(v[i]);
    for (int i = n / 2; i--; ) push_front(v[i]);
  }
  void push_front(T a) { l.push_back(a), cuml.push_back(Op(a, cuml.back())); }
  void push_back(T a) { r.push_back(a), cumr.push_back(Op(cumr.back(), a)); }
  void pop_front() {
    if (l.empty()) build({++begin(r), end(r)});
    else l.pop_back(), cuml.pop_back();
  }
  void pop_back() {
    if (r.empty()) build({++rbegin(l), rend(l)});
    else r.pop_back(), cumr.pop_back();
  }
};

int _min(int a, int b) { return b < a ? b : a; }
int inf() { return 0x3f3f3f3f; }

int main() {
  int n = getint<int>();
  int l = getint<int>();
  FoldableDeque<int, _min, inf> fdeq;
  for (int i = 0; i != n; ++i) {
    fdeq.push_back(getint<int>());
    if (i >= l - 1) {
      putint(fdeq.fold(), " \n"[i == n - 1]);
      fdeq.pop_front();
    }
  }
}