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 <climits>
#include <functional>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <stdlib.h>
#include <string>
#include <time.h>
#include <utility>
#include <vector>

using int32 = std::int_fast32_t;
using int64 = std::int_fast64_t;
using uint32 = std::uint_fast32_t;
using uint64 = std::uint_fast64_t;
using uintl32 = std::uint_least32_t;



template<typename T, size_t bitsize>
class wavelet_matrix {
	std::vector<std::uint_least32_t> dic[bitsize];
	uint32 border[bitsize];
	inline uint32 rank(uint32 i, uint32 index) {
		return dic[i][(index >> 5) << 1] + __builtin_popcount(dic[i][index >> 4 | 1] & ((uintl32)1 << (index & 0x1f)) - 1);
	}
public:
	wavelet_matrix(std::vector<T> &a) {
		const uint32 len = a.size(), block = ((len >> 5) + 1) << 1;
		for (uint32 i = 0; i < bitsize;++i) {
			dic[i] = std::vector<std::uint_least32_t>(block, 0);
		}
		std::queue<T> Q0, Q1;
		for (uint32 i = 0;i < len;++i) {
			Q0.push(a[i]);
		}
		for (uint32 i = bitsize - 1;~i;--i) {
			const uint32 size = Q0.size();
			uint32 j;
			for (j = 0;j < size;++j) {
				if (Q0.front() >> i & 1) {
					dic[i][j >> 4 | 1] |= (std::uint_least32_t)1 << (j & 0x1f);
					Q1.push(Q0.front());
				}
				else {
					Q0.push(Q0.front());
				}
				Q0.pop();
			}
			for (;j < len;++j) {
				if (Q1.front() >> i & 1) {
					dic[i][j >> 4 | 1] |= (std::uint_least32_t)1 << (j & 0x1f);
					Q1.push(Q1.front());
				}
				else {
					Q0.push(Q1.front());
				}
				Q1.pop();
			}
			border[i] = Q0.size();
			for (j = 2;j < block;j+=2) {
				dic[i][j] = dic[i][j - 2] + __builtin_popcount(dic[i][j - 1]);
			}
		}
		return;
	}
	T access(uint32 index) {
		T ret = 0;
		for (uint32 i = bitsize - 1;~i;--i) {
			ret <<= 1;
			if (dic[i][index >> 4 | 1] >> (index & 0x1f) & 1) {
				++ret;
				index = rank(i, index) + border[i];
			}
			else {
				index -= rank(i, index);
			}
		}
		return ret;
	}
	T rank(uint32 begin, uint32 end, T data) {
		for (uint32 i = bitsize - 1;~i;--i) {
			if (data >> i & 1) {
				begin = rank(i,begin) + border[i];
				end = rank(i,end) + border[i];
			}
			else {
				begin -= rank(i, begin);
				end -= rank(i, end);
			}
		}
		return end - begin;
	}
	T quantile(uint32 begin, uint32 end, uint32 k) {
		T ret = 0;
		for (uint32 i = bitsize - 1;~i;--i) {
			const uint32 l = rank(i, begin), r = rank(i, end);
			ret <<= 1;
			if (r - l > k) {
				begin = l + border[i];
				end = r + border[i];
				++ret;
			}
			else {
				begin -= l;
				end -= r;
				k -= r - l;
			}
		}
		return ret;
	}
	T rquantile(uint32 begin, uint32 end, uint32 k) {
		return quantile(begin, end, end - begin - k - 1);
	}
};

int main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	uint32 n, l;
	std::cin >> n >> l;
	std::vector<uint32> a(n);
	for (uint32 i = 0;i < n;++i) {
		std::cin >> a[i];
	}
	wavelet_matrix<uint32, 30> T(a);
	std::cout << T.rquantile(0, l, 0);
	for (uint32 i = 1;i < n - l + 1;++i) {
		std::cout << " " << T.rquantile(i, i + l, 0);
	}
	std::cout << "\n";
	return 0;
}