#include<cstdio>
#include<string>
#include<cstring>
#include<deque> 
#include<iostream>
#define maxn 1000005
using namespace std;
int a[maxn];
int main(){
	freopen("window.in","r",stdin);
	freopen("window.out","w",stdout);
	int k,n,x,y,f,b;
	deque<int>h,l;
	scanf("%d%d",&n,&k);
	if(k>n)k=n;//鲁棒性，如果区间比数量大，把数量赋值给区间 
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	h.push_front(1);
	l.push_front(1);//把第一个进去 ，因为只有一个，必是最大和最小 
	for(int i=2;i<=k;i++){
		while(y=h.back(),a[y]<=a[i]){
			h.pop_back();
			if(h.empty())break;
		}//因为1一开始入队 ，所以一定非空
		//将队尾比自己小或相等的去掉（以为自己后过期，当自己过期时 ，一定删掉的早已过期，无法继承） 
		h.push_back(i);//将自己进去，因为自己可能继承 
		while(x=l.back(),a[x]>=a[i]){
			l.pop_back();
			if(l.empty())break;
		}//因为1一开始入队 ，所以一定非空
		//将队尾比自己大的或相等的去掉（以为自己后过期，当自己过期时 ，一定删掉的早已过期，无法继承） 
		l.push_back(i);//将自己进去，因为自己可能继承
	}//把前k个压进去 
	printf("%d ",a[l.front()]);//输出第一个区间最小值 
	for(int i=k+1;i<=n;i++){
		b=l.front();//检查队首是否过期 
		if(b==i-k)l.pop_front();//因为队后的一定比队首晚入，所以只需判断队首 
		if(l.empty())l.push_front(i);//如果队空了，直接压进去 
		else {
			while(x=l.back(),a[x]>=a[i]){
				l.pop_back();
				if(l.empty())break;
			}//将队尾比自己大的或相等的去掉（以为自己后过期，当自己过期时 ，一定删掉的早已过期，无法继承） 
			l.push_back(i);//把自己加进去 
		} 
		printf("%d ",a[l.front()]);//输出区间最小值 
	}//处理最小值 
	printf("\n%d ",a[h.front()]);//输出第一个区间最大值 
	for(int i=k+1;i<=n;i++){
		f=h.front();//检查队首是否过期
		if(f==i-k)h.pop_front();//因为队后的一定比队首晚入，所以只需判断队首
		if(h.empty())h.push_front(i);//如果队空了，直接压进去
		else {
			while(y=h.back(),a[y]<=a[i]){
				h.pop_back();
				if(h.empty())break;
			}//将队尾比自己小或相等的去掉（以为自己后过期，当自己过期时 ，一定删掉的早已过期，无法继承） 
			h.push_back(i);//把自己加进去 
		} 
		printf("%d ",a[h.front()]);//输出区间最大值 
	}//处理最大值 
}