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:
#define NDEBUG
#include <cassert>
#include <vector>

template <typename SemiLattice> class SparseTable {
public:
	using value_type = SemiLattice;
	using container_type = std::vector<value_type>;
	using size_type = typename container_type::size_type;

private:
	static size_type clz32(size_type c) {
#ifdef __GNUC__
		return 31 ^ __builtin_clz(c);
#else
		size_type ret = 0;
		if (c & 0xFFFF0000)
			c &= 0xFFFF0000, ret |= 16;
		if (c & 0xFF00FF00)
			c &= 0xFF00FF00, ret |= 8;
		if (c & 0xF0F0F0F0)
			c &= 0xF0F0F0F0, ret |= 4;
		if (c & 0xCCCCCCCC)
			c &= 0xCCCCCCCC, ret |= 2;
		if (c & 0xAAAAAAAA)
			ret |= 1;
		return ret;
#endif
	}
	std::vector<container_type> matrix;

public:
	SparseTable(const container_type &a)
		: matrix(a.empty() ? 0 : clz32(a.size()) + 1) {
		if (!a.empty())
			matrix[0].reserve(a.size());
		for (size_type i = 0; i < a.size(); ++i)
			matrix[0].emplace_back(a[i]);
		for (size_type i = 1; i < matrix.size(); ++i) {
			const size_type msiz = a.size() + 1 - (static_cast<size_type>(1) << i);
			matrix[i].reserve(msiz);
			for (size_type j = 0; j < msiz; ++j)
				matrix[i].emplace_back(
					matrix[i - 1][j] +
					matrix[i - 1][j + (static_cast<size_type>(1) << (i - 1))]);
		}
	}
	value_type range(const size_type begin, const size_type end) const {
		assert(begin < end);
		assert(begin < size());
		assert(end <= size());
		const size_type t = clz32(end - begin);
		return matrix[t][begin] + matrix[t][end - (static_cast<size_type>(1) << t)];
	}
	size_type size() const noexcept { return empty() ? 0 : matrix[0].size(); }
	bool empty() const noexcept { return matrix.empty(); }
};
#include <algorithm>
#include <limits>
template <typename T> struct Mini {
	using value_type = T;
	T a;
	explicit Mini(const T &x = std::numeric_limits<T>::max()) : a(x) {}
	Mini operator+(const Mini &o) const { return Mini(std::min(a, o.a)); }
};
#include<cstdio>
#include<vector>
int main() {
	using M = Mini<int>;
	int n, l;
	scanf("%d %d", &n, &l);
	std::vector<M> a(n);
	for (auto &x : a)scanf("%d", &x.a);
	SparseTable<M> T(a);
	for (int i = 0;i <= n - l;++i)
		printf("%d%c", T.range(i, i + l).a, " \n"[i == n - l]);
	return 0;
}