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 <algorithm>

#define NMAX 1000000
#define LMAX 1000000
#define DMAX 1000000000

using namespace std;

int Input(vector<int>&);
void CreateTree(vector<vector<int> >&, int);
void UpDate(vector<vector<int> >&, int, int);

int main(){
    vector<int> data;
    vector<vector<int> > tree(1);
    int L = Input(data);
    
    if(L == -1)
        return -1;
    
    copy(data.begin(), data.begin() + L, back_inserter(tree[0]));
    if(tree[0].size() > 1)
        CreateTree(tree, 0);
    
    cout << tree[tree.size() - 1][0];
    for(vector<int>::size_type i = 1; i <= data.size() - L; i++){
        UpDate(tree, (i - 1) % L, data[i - 1 + L]);
        cout << " " << tree[tree.size() - 1][0];
    }
    
    cout << endl;
    
    return 0;
}

int Input(vector<int> &data){
    int N, L, a;
    
    cin >> N >> L;
    if(!(1 <= N && N <= NMAX) || !(1 <= L && L <= LMAX) || L > N)
        return -1;
    
    for(int i = 0; i < N; i++){
        cin >> a;
        if(!(1 <= a && a <= DMAX))
            return -1;
        data.push_back(a);
    }
    
    return L;
}

void CreateTree(vector<vector<int> > &tree, int level){
    vector<int> new_layer;
    
    for(vector<int>::size_type i = 0; i < tree[level].size(); i += 2){
        new_layer.push_back(min(tree[level][i], tree[level][i + 1]));
        
        if(i + 2 == tree[level].size() - 1){
            new_layer.push_back(tree[level][i + 2]);
            break;
        }
    }
    
    tree.push_back(new_layer);
    
    if(tree[level + 1].size() > 1)
        CreateTree(tree, level + 1);
}

void UpDate(vector<vector<int> > &tree, int i, int v){
    int target = i;
    tree[0][target] = v;
    
    for(vector<vector<int> >::size_type level = 1; level < tree.size(); level++){
        if(target == tree[level - 1].size() - 1 && tree[level - 1].size() & 1)
            tree[level][target / 2] = tree[level - 1][target];
        else if(target & 1)
            tree[level][target / 2] = min(tree[level - 1][target], tree[level - 1][target - 1]);
        else
            tree[level][target / 2] = min(tree[level - 1][target], tree[level - 1][target + 1]);
        
        target /= 2;
    }
}