#include<iostream>
#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;

int a[1000010];
int m,n;
deque<int> q; 
deque<int> p;
	
void Get_min(int i){
	if(i<m){
		if(p.empty()) p.push_back(i);
		else{
			if(a[i]>=a[p.back()]) p.push_back(i);
			else if(a[i]<a[p.back()]){
				while(!p.empty() && a[i]<a[p.back()]) p.pop_back();
				p.push_back(i);
			} 
		}
	}
	else if(i==m){
		if(a[i]>=a[p.back()]) p.push_back(i);
		else if(a[i]<a[p.back()]){
			while(!p.empty() && a[i]<a[p.back()]) p.pop_back();
			p.push_back(i);
		}
		printf("%d ",a[p.front()]);
	}
	else if(i>m){
		int j=i-m;
		if(p.front()==j) p.pop_front();
		else if(p.back()==j) p.pop_back();
		if(p.empty()) p.push_back(i);
		else if(a[i]>=a[p.back()]) p.push_back(i);
		else if(a[i]<a[p.back()]){
			while(!p.empty() && a[i]<a[p.back()]) p.pop_back();
			p.push_back(i);
		}
		printf("%d ",a[p.front()]);
	}
}

void Get_max(int i){
	if(i<m){
		if(q.empty())q.push_back(i);
		else if(a[i]<=a[q.back()]) q.push_back(i);
		else if(a[i]>a[q.back()]){
			while(!q.empty() && a[i]>a[q.back()]) q.pop_back();
			q.push_back(i);
		}
	}
	else if(i==m){
		if(q.empty())q.push_back(i);
		else if(a[i]<=a[q.back()]) q.push_back(i);
		else if(a[i]>a[q.back()]){
			while(!q.empty() && a[i]>a[q.back()]) q.pop_back();
			q.push_back(i);
		}
		printf("%d ",a[q.front()]);
	}
	else if(i>m){
		int j=i-m;
		if(q.front()==j) q.pop_front();
		else if(q.back()==j) q.pop_back();
		if(q.empty())q.push_back(i);
		else if(a[i]<=a[q.back()]) q.push_back(i);
		else if(a[i]>a[q.back()]) {
			while(!q.empty() && a[i]>a[q.back()]) q.pop_back();
			q.push_back(i);
		}
		printf("%d ",a[q.front()]);
	}
} 

int main(){
	freopen("window.in","r",stdin);
	freopen("window.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		Get_min(i);
	}
	printf("\n");
	for(int i=1;i<=n;i++)Get_max(i);
	fclose(stdin);fclose(stdout);
	return 0;
}