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 <cassert>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <random>
#include <memory>
#include <utility>
#include <limits>
 
#define rep(i, a, b) for (long long (i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cerr << "debug " <<"LINE:"<<__LINE__<<"  "<< #i <<":"<< i << std::endl

 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}
 
long long pow_mod(long long a, long long b, long long mod=-1) {
  if ((a == 0)||(mod!=-1&&a%mod==0)) {
    return 0;
  }
 
  long long x = 1;
 
  while (b > 0) {
    if (b & 1) {
      x = (mod!=-1)?(x * a) % mod:x*a;
    }
    a = (mod!=-1)?(a * a) % mod:a*a;
    b >>= 1;
  }
  return x;
}
 
// const long long MOD = 998244353;
const long long MOD = 1e9 + 7;

using ll = long long;
using P = std::pair<ll, ll>;

template<typename T>
class SWAG{
  private:

  std::function<T(T,T)> fn;

  std::stack<T> front,back;
  std::vector<T> front_fold,back_fold;

  T id;

  public:

  SWAG(T id_,std::function<T(T,T)> fn_):id(id_),fn(fn_),front_fold(1,id_),back_fold(1,id_){}

  void push(T val){
    back.push(val);
    back_fold.push_back(fn(back_fold.back(),val));
  }

  void pop(){
    if(front.empty()){
      assert(front_fold.size()==1);
      while(!back.empty()){
        T temp=back.top();
        back.pop();
        back_fold.pop_back();

        front.push(temp);
        front_fold.push_back(fn(temp,front_fold.back()));
      }
    }

    assert(!front.empty());

    front.pop();
    front_fold.pop_back();
    
  }

  T fold_all(){
    return fn(front_fold.back(),back_fold.back());
  }
};

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  ll n,l;
  std::cin>>n>>l;

  SWAG<ll> swag(MOD,[](ll a,ll b){return std::min(a,b);});

  rep(i,0,l-1){
    ll a;
    std::cin>>a;
    swag.push(a);
  }

  rep(i,0,n+1-l){
    ll a;
    std::cin>>a;
    swag.push(a);
    std::cout<<swag.fold_all();
    if(i!=n-l)std::cout<<" ";
    swag.pop();
  }

  std::cout<<"\n";

  return 0;
}