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:
#line 1 "sparse_table.test.cpp"
#include <cstdio>
#include <algorithm>
using namespace std;

#define call_from_test
#line 2 "/mnt/hdd1/cpp_library/structure/strc_007_sparsetable.cpp"

// @brief Sparse Table
// @docs ./docs/sparse_table.md

#include <vector>
#include <functional>
#include <cassert>

template <typename Tp>
struct SparseTable {
    size_t N, LN;
    vector<Tp> A, logs;
    vector< vector<Tp> > node;
    function<Tp(Tp, Tp)> f;

    SparseTable() = default;
    SparseTable(vector<Tp> A_, function<Tp(Tp, Tp)> f_) :
        A(A_), f(f_) {
        N = LN = 1;
        while(N < A.size()) N <<= 1, LN++;
        N = A.size();
        logs.resize(N+1);
        node.resize(N, vector<int>(LN));
        build();
    }

    void build() {
        for(size_t i=2; i<N; i++) {
            logs[i] = logs[i>>1] + 1;
        }
        for(size_t i=0; i<N; i++) {
            node[i][0] = A[i];
        }
        for(size_t k=0; k+1<LN; k++) {
            for(size_t i=0; i+(1<<k)<N; i++) {
                Tp x = node[i][k];
                Tp y = node[i+(1<<k)][k];
                node[i][k+1] = f(x, y);
            }
        }
    }

    inline Tp query(size_t l, size_t r) {
        assert(l < r and r <= N);
        int d = logs[r-l];
        Tp x = node[l][d];
        Tp y = node[r-(1<<d)][d];
        return f(x, y);
    }
};
#line 7 "sparse_table.test.cpp"
#undef call_from_test

int main() {
    int N, L; scanf("%d%d", &N, &L);
    vector<int> A(N);
    for(int i=0; i<N; i++) scanf("%d", &A[i]);

    SparseTable<int> sp(A, [](int x, int y) { return min(x, y); });
    for(int i=0; i<N-L+1; i++) {
        printf("%d%c", sp.query(i, i+L), " \n"[i == N-L]);
    }
    return 0;
}