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>
#define MAX 2000010
#define inf 2147483647
#define linf (1e16)
#define eps (1e-8)
#define Eps (1e-12)
#define mod 1000000007
#define pi acos(-1.0)
#define phi (1.0+sqrt(5.0))/2.0
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define pd(a) printf("%.10f\n",(double)(a))
#define pld(a) printf("%.10Lf\n",(ld)(a))
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(a)-1;(b)<=i;i--)
#define Unique(v) v.erase(unique(all(v)),v.end())
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,double> pid;
typedef pair<double,int> pdi;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<pii> vpi;

int n,n_,L;
int st[MAX*2];

void init(){
  n_ = 1;
  while(n_<n)n_*=2;
  FOR(i,0,2*n_-1)st[i]=inf;
}

void update(int a,int b){
  a+=n_-1;
  st[a] = b;
  while(a>0){
    a = (a-1)/2;
    st[a] = min(st[a*2+1],st[a*2+2]);
  }
}

int find(int a,int b,int c,int l,int r){
  if(r<=a || b<=l)return inf;
  if(a<=l && r<=b)return st[c];
  
  int L = find(a,b,c*2+1,l,(l+r)/2);
  int R = find(a,b,c*2+2,(l+r)/2,r);
  return min(L,R);
}

void solve(){
  FOR(i,0,n-L+1){
    cout<<find(i,i+L,0,0,n_);
    if(i!=n-L)cout<<" ";
  }
  cout<<endl;
}

int main()
{
  cin>>n>>L;
  init();
  FOR(i,0,n){
    int a;
    cin>>a;
    update(i,a);
  }
  solve();
  return 0;
}