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;

#define ll long long

/* Sparse Tableを利用したRangeMinimumQuery */
template <typename T>
struct RMinQ_SparseTable {
private:
	// log_table : logの値
	// table[i][k] : インデックスiから長さ1<<kの最小値のインデックス
	vector<int> log_table;
	vector<vector<int>> table;
public:
	// n : 要素数
	// element : 要素
	int n;
	vector<T> element;
	// コンストラクタ
	RMinQ_SparseTable(vector<T> vec) {
		n = vec.size();
		element.resize(n);
		for (int i = 0; i < n; ++i)
			element[i] = vec[i];
		// log_tableを構築
		log_table.resize(n + 1, 0);
		for (int i = 2; i <= n; ++i)
			log_table[i] = log_table[i >> 1] + 1;
		// tableを構築
		table.resize(n, vector<int>(log_table[n] + 1));
		for (int i = 0; i < n; ++i)
			table[i][0] = i;
		for (int k = 1; (1 << k) <= n; ++k) {
			for (int i = 0; i + (1 << k) <= n; ++i) {
				int c1 = table[i][k - 1], c2 = table[i + (1 << (k - 1))][k - 1];
				if (element[c1] < element[c2]) table[i][k] = c1;
				else table[i][k] = c2;
			}
		}
	}
	// [l, r)の範囲の最小値のインデックスを求める
	int query_idx(int l, int r) {
		int d = r - l;
		int k = log_table[d];
		if (element[table[l][k]] < element[table[r - (1 << k)][k]])
			return table[l][k];
		return table[r - (1 << k)][k];
	}
	// [l,r)の範囲の最小値を求める
	T query_value(int l, int r) {
		return element[query_idx(l, r)];
	}
};

int main() {
	int N, L; cin >> N >> L;
	vector<int> a(N);
	for (int i = 0; i < N; ++i) cin >> a[i];

	RMinQ_SparseTable<int> st(a);
	for (int i = 0; i <= N - L; ++i) {
		cout << st.query_value(i, i + L);
		if (i != N - L) cout << " ";
	}
	cout << endl;

	return 0;
}