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 <algorithm>
#include <array>
#include <cstdint>
#include <functional>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <vector>

#define INF 1000000000
#define MOD 1000000007
#define ll long long
#define rep(i,a,b) for(int32 i = (a); i < (b); ++i)
#define rrep(i,a,b) for(int32 i = (b) - 1; i >= (a); --i)
#define bitget(a,b) (((a) >> (b)) & 1)
#define vint vector<int>
#define ALL(x) (x).begin(),(x).end()
#define C(x) cout << #x << ":" << x << endl
#define scanf scanf_s

using int32 = int_fast32_t;
using int64 = int_fast64_t;
using uint32 = uint_fast32_t;
using uint64 = uint_fast64_t;

using namespace std;

template<typename Monoid, typename Operand>
class SegTree {
public:
	Monoid* tree;
	size_t size;
	int32 i;
	//?????????????????????
	SegTree(size_t length) {
		--length;
		size = length;
		if (size & 0xffff0000) { size = size & 0xffff0000; }
		if (size & 0xff00ff00) { size = size & 0xff00ff00; }
		if (size & 0xf0f0f0f0) { size = size & 0xf0f0f0f0; }
		if (size & 0xcccccccc) { size = size & 0xcccccccc; }
		if (size & 0xaaaaaaaa) { size = size & 0xaaaaaaaa; }
		if (length) { size <<= 1; }
		else { size = 1; }
		tree = (Monoid *)calloc(size << 1, sizeof(Monoid));
	}
	//?????????
	void set(bool merge) {
		i = size << 1;
		while (--i) { tree[i].set(); }
		if (merge) {
			i = size;
			while (--i) { tree[i] = tree[i << 1] + tree[i << 1 | 1]; }
		}
	}
	//tree[index]???data???§???´???°
	void update(size_t index, Operand &data) {
		index += size;
		tree[index] = tree[index] * data;
		while (index >>= 1) tree[index] = tree[index << 1] + tree[index << 1 | 1];
	}
	//[begin,end)??????????????????
	Monoid range(size_t begin, size_t end) {
		Monoid retL, retR;
		for (begin += size, end += size; begin < end; begin >>= 1, end >>= 1) {
			if (begin & 1) retL = retL + tree[begin++];
			if (end & 1)  retR = tree[end - 1] + retR;
		}
		return retL + retR;
	}
};
struct SUB {
	int32 e;
	SUB() { set(); }
	SUB(int32 x) { e = x; }
	void set() { e = 1000000000; }
	SUB operator*(const SUB &other) {
		return other;
	}
};
struct MIN {
	int32 e;
	MIN() { set(); }
	MIN(int32 x) { e = x; }
	void set() { e = 2147483647; }
	MIN operator+(const MIN &other) {
		if (e < other.e) return *this;
		return MIN(other.e);
	};
	MIN operator*(const SUB &other) {
		return MIN(other.e);
	}
};

int main() {
	int32 n, l;
	cin >> n >> l;
	SUB a;
	SegTree<MIN, SUB> t(n);
	rep(i, 0, n){
		cin >> a.e;
		t.update(i, a);
	}
	printf("%d", t.range(0, l).e);
	rep(i, 1, n - l + 1)
		printf(" %d", t.range(i, i + l).e);
	printf("\n");
	return 0;
}