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;
using ll = long long;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

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


struct player
{
    string name;
    int time;
    int total;
    vector<int> points;
};

int main()
{

#ifdef DEBUG
    cout << "DEBUG MODE" << endl;
    ifstream in("input.txt"); //for debug
    cin.rdbuf(in.rdbuf());    //for debug
#endif

    int n, l, a, t;
    cin >> n >> l;
    int num[n];
    deque<PII> deq;

    rep(i, n)
    {
        cin >> a;
        t = l + i;
        while (!deq.empty())
        {
            if (deq.front().second <= i)
                deq.pop_front();
            else
                break;
        }
        while (!deq.empty())
        {
            if (deq.back().first >= a)
                deq.pop_back();
            else
                break;
        }
        deq.push_back(make_pair(a, t));

        if (i >= l - 1)
        {
            cout << deq.front().first;
            if (i != n - 1)
                cout << " ";
            else
                cout << endl;
        }
        // for (auto z : deq)
        //     cout << z.first << " ";
        // cout << endl;
    }
    
    return 0;
}