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 <stdio.h>
#include <assert.h>

namespace beet{
  
  template<typename T>
  void swap(T &a,T &b){
    T x=a;
    a=b;
    b=x;
  }
  
  template<typename T>
  struct Vector{
    int sz,cap;
    T *data;
    Vector():sz(0),cap(1){
      data = new T[cap];
    }    
    Vector(int sz):sz(sz),cap(sz<<1){
      data = new T[cap];
    }
    Vector(int sz,T t):sz(sz),cap(sz<<1){
      data = new T[cap];
      for(int i=0;i<sz;i++) data[i]=t;
    }
    ~Vector(){
      delete[] data;
    }
    void resolve(){
      T *tmp = new T[cap];
      for(int i=0;i<sz;i++) tmp[i]=data[i];
      delete[] data;
      data=tmp;
    }
    void resize(int nsz){
      cap=nsz<<1;
      if(sz>cap) sz=cap;
      resolve();      
    }
    void assign(int nsz,T t){
      resize(nsz);
      sz=nsz;
      for(int i=0;i<sz;i++) data[i]=t;
    }    
    void push_back(T x){
      if(sz>=cap){
        cap<<=1;
        assert(sz<cap);
        resolve();
      }      
      data[sz++]=x;
    }
    void pop_back(){
      sz--;
    }
    int size() const{
      return sz;
    }
    const T operator[](int x) const{
      return data[x];
    }
    T& operator[](int x){
      assert(0<=x&&x<sz);
      return data[x];
    }
  };
  
  template <typename T, typename F>
  struct SegmentTree{
    int n;
    F f;
    T ti;
    Vector<T> dat;
    SegmentTree(){};
    SegmentTree(F f,T ti):f(f),ti(ti){}
    void init(int n_){    
      n=1;
      while(n<n_) n<<=1;
      dat.assign(n<<1,ti);
    }
    void build(const Vector<T> &v){
      int n_=v.size();
      init(n_);
      for(int i=0;i<n_;i++) dat[n+i]=v[i];
      for(int i=n-1;i;i--)
        dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
    }
    void set_val(int k,T x){
      dat[k+=n]=x;
      while(k>>=1)
        dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);    
    }
    T query(int a,int b){
      T vl=ti,vr=ti;
      for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
        if(l&1) vl=f(vl,dat[l++]);
        if(r&1) vr=f(dat[--r],vr);
      }
      return f(vl,vr);
    }
  };

}
//INSERT ABOVE HERE
using namespace beet;

int main(){
  int n,l;
  scanf("%d %d",&n,&l);
  Vector<int> as(n);
  for(int i=0;i<n;i++) scanf("%d",&as[i]);
  
  int ti=(1LL<<31)-1;
  auto f=[](int a,int b){return a<b?a:b;};
  SegmentTree<int, decltype(f)> seg(f,ti);
  seg.build(as);
  
  for(int i=0;i+l<=n;i++){
    if(i) printf(" ");
    printf("%d",seg.query(i,i+l));
  }
  puts("");
  return 0;
}