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 <vector>
#include <cmath>
#include <sstream>

using namespace std;

int initv = pow(10, 9);
vector< vector<int> > segment_tree;
pair<int, int> dummy = make_pair(-1, initv);

pair<int, int> query(int a, int b, int k, int l, int r){
	if(r<=a || b<=l) return dummy;
	if(a<=l && r<=b) return make_pair(segment_tree[k][0], segment_tree[k][1]);

	pair<int, int> vl, vr;
	vl = query(a, b, k*2+1, l, int((l+r)/2));
	vr = query(a, b, k*2+2, int((l+r)/2), r);
	if(vl.second < vr.second) return vl;
	else return vr;
}


int main(void){

	// input N & L
	int n, l;
	cin >> n >> l;
	cin.ignore();

	int n_ = 1;
	while(n_ < n){
		n_ *= 2;
	}

	
	segment_tree = vector< vector<int> >(2*n_-1, vector<int>(2, initv)); // makesegment tree

	string s;
	getline(cin, s); // input series
	stringstream ss;
	ss << s;

	// take in input to segment tree
	for(int i=0 ; i < n ; i++){
		int a;
		ss >> a;
		segment_tree[n_-1+i][0] = i;
		segment_tree[n_-1+i][1] = a;
	}

	// initialize segment tree
	for(int i = n_-2 ; i >= 0 ; i--){
		if(segment_tree[i*2+1][1] < segment_tree[i*2+2][1]){
			segment_tree[i][0] = segment_tree[i*2+1][0];
			segment_tree[i][1] = segment_tree[i*2+1][1];
		}
		else{
			segment_tree[i][0] = segment_tree[i*2+2][0];
			segment_tree[i][1] = segment_tree[i*2+2][1];
		}
	}


	pair<int, int> current_min;
	current_min = dummy; // current_min[0]:id of current min, current_min[1]:value of current min
	for(int i=0 ; ; i++ ){

		// if current_min is out of range, search new current_min
		if(current_min.first < i){
			current_min = query(i, i+l, 0, 0, n_);
		}

		// else, compare current_min and new end
		else{
			if(current_min.second >= segment_tree[n_+i+l-2][1]){
				current_min = make_pair(segment_tree[n_+i+l-2][0], segment_tree[n_+i+l-2][1]);
			}
		}

		cout << current_min.second;

		if(i+l == n){
			cout << endl;
			break;
		}
		else cout << ' ';
	}

}