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<iostream>
#include<vector>
#include<cassert>

template<class T>
struct disjoint_sparse_table{
  std::vector<std::vector<T>> table;
  size_t sz;
  static size_t msb(size_t c){
  #ifdef __has_builtin
    return 31 - __builtin_clz(c);
  #else
    size_t res = 0;
    if(c>>16)c>>=16,res+=16;
    if(c>>8)c>>=8,res+=8;
    if(c>>4)c>>=4,res+=4;
    if(c>>2)c>>=2,res+=2;
    return res+(c>>1);
  #endif
  }
  T f(T a,T b)const{
    return a<=b?a:b;
  }
  disjoint_sparse_table():table(){}
  disjoint_sparse_table(std::vector<T> const& v):table(){
    table.emplace_back(v);
    const size_t size = table.front().size();
    sz = size;
    for(int i=2;i<size;i<<=1){
      std::vector<T> v;
      v.reserve(size);
      for(int j=i;j<size;j+=i<<1){
        v.emplace_back(table.front()[j-1]);
        for(int k=2;k<=i;++k){
          v.emplace_back(f(table.front()[j-k],v.back()));
        }
        v.emplace_back(table.front()[j]);
        for(int k=1;k<i&&j+k<size;++k){
          v.emplace_back(f(v.back(),table.front()[j+k]));
        }
      }
      table.emplace_back(std::move(v));
    }
  }
  T fold(int a,int b)const{
    assert(a<=b);
    assert(b<sz);
    if(a==b){
      return table.front()[a];
    }
    int p = msb(a^b);
    return f(table[p][a^(static_cast<size_t>(1)<<p)-1],table[p][b]);
  }
  T operator[](int i)const{
    return table.front()[i];
  }
};

signed main(){
  using namespace std;
  int n,l;
  cin>>n>>l;
  vector<int> a(n);
  for(auto& ai:a)cin>>ai;
  disjoint_sparse_table<int> dst(a);
  
  for(int i=0;i<=n-l;++i){
    cout<< dst.fold(i,i+l-1) <<" \n"[i==n-l];
  }

}