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>
using namespace std;
#define FOR(I,X,Y) for(long long (I)=(X);(I)<(Y);(I)++)
#define REP(I,X,Y) for(long long (I)=(Y)-1;(I)>=(X);(I)--)
#define ALL(X) (X).begin(),(X).end()
#define pb push_back
#define COUNT(V,X) upper_bound((V).begin(),(V).end(),X)-lower_bound((V).begin(),(V).end(),X)
#define debug(x) cerr<<#x<<':'<<x<<endl;
#define DEBUG(v) cerr<<#v<<':';for(auto xXx:v)cerr<<xXx<<' ';cerr<<endl;
#define INF 1000000007
#define LINF 1000000000000000007
#define Yes(X) if(X){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define YES(X) if(X){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define ctoi(C) (C-'0')
typedef long long ll;
typedef long double ld;
long long dx[] = {1,0,-1,0};
long long dy[] = {0,1,0,-1};
long long dx8[] = {1,1,0,-1,-1,-1,0,1};
long long dy8[] = {0,1,1,1,0,-1,-1,-1};
long long dx9[] = {1,1,0,-1,-1,-1,0,1,0};

struct SparseTable{
    long long merge(long long x,long long y){
        return min(x,y);
    }
    vector<vector<long long>> table;
    vector<int> log_table;
    SparseTable(vector<long long> A) : table(){
        log_table.resize(A.size()+1);
        log_table[1] = 0;
        for(int i = 2;i <= A.size();i++){
            log_table[i] = log_table[i/2] + 1;
        }
        table.resize(A.size());
        fill(table.begin(),table.end(),vector<long long>(log_table[A.size()]+1));
        for(int i = 0;i < A.size();i++)table[i][0] = A[i];
        for(int i = 1;(1 << i) <= A.size();i++){
            for(int j = 0;j+(1<<i) <= A.size();j++){
                table[j][i] = merge(table[j][i-1],table[j+(1<<(i-1))][i-1]);
            }
        }
    }
    long long query(long long i,long long j){
        return merge(table[i][log_table[j-i+1]],table[j-(1 << log_table[j-i+1])+1][log_table[j-i+1]]);
    }
};

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,L;
    cin >> N >> L;
    vector<long long> a(N);
    FOR(i,0,N)cin >> a[i];
    SparseTable st(a);
    FOR(i,0,N-L)cout << st.query(i,i+L-1) << ' ';
    cout << st.query(N-L,N-L+L-1) << endl;
}