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>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)

typedef long long ll;

#define INF (1e18)

struct RMQ {
    ll n;
    vector<ll> node;

    RMQ(ll *a_,ll n_) {
        vector<ll> a;
        rep(i,n_)a.push_back(a_[i]);
        initialize(a);
    }
    RMQ(vector<ll> a) {
        initialize(a);
    }

    void initialize(vector<ll> a) {
        ll n_ = (ll)a.size();
        n = 1;
        while(n<n_)n *= 2;

        node.resize(2*n,INF);

        rep(i,n_) node[n + i] = a[i];
        for(int i=n-1;i > 0;i--)node[i] = min(node[2*i],node[2*i+1]);
    }

    void update(ll k,ll a) {// k番目(0-indexed)の値をaに更新
        k += n;
        node[k] = a;

        while(k > 1) {
            k /= 2;
            node[k] = min(node[k * 2],node[k * 2 + 1]);
        }
    }

    ll query(ll a,ll b,ll k=1,ll l=0,ll r=0) {//query(a,b) min{ node[i] | i∈[a,b) } を返す
        //k  節点のインデックス
        //その節点が[l,r)に対応づいている
        if(l>=r)r = n;//外から呼ばれる時 l=0,r=nとする必要があるのでこうなる。
        if(r <= a || b <= l)return INF;//範囲外
        if(a <= l && r <= b)return node[k]; //[a,b)に[l,r)が含まれる

        ll vl = query(a,b,2 * k,l,(l + r) / 2);
        ll vr = query(a,b,2 * k + 1,(l + r) / 2,r);
        return min(vl,vr);
    }
    void print() {
        for(int i = 1;i < 2 * n;i++) {
            if(__builtin_popcount(i) == 1)
                cerr << endl;
            cerr << node[i] << " ";
        }
        cerr << endl;
    }
};

ll n,L;
ll a[1000000];

int main() {
    cin >> n >> L;

	rep(i,n)cin >> a[i];

	RMQ rmq(a,n);

	rep(i,n - L + 1) {
		cout << rmq.query(i,i+L);
		if(i < n - L)cout << " ";
	}
	cout << endl;

    return 0;

}