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 <sstream>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>
using namespace std;
#define MAX LONG_MAX
long aray[4000000];
int n,p=2;

int right(int k){
  return 2*k+2;
}
int left(int k){
  return 2*k+1;
}
int parent(int k){
  return (k-1)/2;
}
long query(int a,int b,int k,int l,int r){
  long res;
  //if (n==1)res = aray[0];
  if(r<=a || b<=l)res = MAX;
  else if(a<=l && r<=b){
      res = aray[k];
      //cout<<"k:"<<k<<" res:"<<res<<endl;
  }
  else {
      res = min(query(a,b,left(k),l,(l+r)/2),query(a,b,right(k),(l+r)/2,r));
      //cout<<"res"<< res<<" l:"<<l<<" r:"<<r<<endl;
  }
  return res;   
}
long findmin(int a,int b){
    return query(a,b,0,0,p);
}
void update(int k,long x){
  k = k+p-1;
  aray[k] =x;
  while(k>0){
    k=parent(k);
    aray[k]=min(aray[left(k)],aray[right(k)]);
  }
}
void check(){
    int k=1,c=1;
    cout<<"---------------"<<endl;
  for(int i=0;i<2*p-1;i++){
      cout<<aray[i]<<" ";
      k++;
      if(k%c==0){
          cout<<endl;
          k=0;
          c*=2;
      }
  }
  cout<<endl;
}
int main(){
  int l,i=0,j;
  long tmp;
  cin>>n>>l;
  while(n>pow(p,i))i++;
  p= pow(p,i);
  for(i=0;i<p*2+1;i++)aray[i]=MAX;
  for(i=0;i<n;i++){
      cin>>tmp;
      update(i,tmp);
  }
  for(i=0;i<n-l+1;i++){
    //cout<<"---------------"<<endl;
    cout<<findmin(i,i+l);
    if(i!=n-l)cout<<" ";
  }
  cout<<endl;
      //cout<<"---------------"<<endl;
      //check();
  return 0;
}