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 <limits>
#include <cmath>

using namespace std;

const int INF = numeric_limits<int>::max();

// [begin, end) of an array
// [left, right): range of the query
// current_idx: index of the node in segment_tree corresponding to a range in the original array
int query(int segment_tree[], int left, int right, int current_idx, int begin, int end){
	if(end <= left || begin >= right){
		return INF;
	}
	if(left <= begin && right >= end){
		return segment_tree[current_idx];
	}

	int left_val = query(segment_tree, left, right, 2 * current_idx + 1, begin, (begin + end) / 2); // value of the left child (left half range)
	int right_val = query(segment_tree, left, right, 2 * current_idx + 2, (begin + end) / 2, end); // value of the right child (right half range)
	return min(left_val, right_val);
}

// [left, right]
int find(int segment_tree[], int n, int left, int right){
	return query(segment_tree, left, right + 1, 0, 0, n);
}

void update(int segment_tree[], int n, int i, int x){
	int current_idx = i + n - 1; // tree index corresponding to the element i in array A
	segment_tree[current_idx] = x;
	while(current_idx > 0){
		current_idx = (current_idx - 1) / 2; // get the parent index
		segment_tree[current_idx] = min(segment_tree[2 * current_idx + 1], segment_tree[2 * current_idx + 2]); // update the child nodes
	}
}

int initRMQ(int original_size){
	int n = 1;
	// make the size of the array to be power of n
	while(n < original_size){
		n *= 2;
	}
	return n;
}

int main(){
	int original_size, L;
	cin >> original_size >> L;
	int n = initRMQ(original_size);
	int segment_tree[2 * n - 1];
	
	for(auto i = 0; i < 2 * n - 1; ++i){
		segment_tree[i] = INF;
	}

	for(auto i = 0; i < original_size; ++i){
		int x;
		cin >> x;
		update(segment_tree, n, i, x);
	}

	for(auto i = 0; i <= original_size - L; ++i){
		cout << find(segment_tree, n, i, i + L - 1);
		if(i == original_size - L) continue;
		cout << " ";
	}
	cout << endl;
}