#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#define maxx 1000000+5

using namespace std;

int size=0,b[maxx];
int a[maxx],n,k;
deque<int>qmax;
deque<int>qmin;

void pop(int x)
{
	while(!qmax.empty() && a[x]>=a[qmax.back()]) qmax.pop_back();
	qmax.push_back(x);
}

void pop2(int x)
{
	while(!qmin.empty() && a[x]<=a[qmin.back()]) qmin.pop_back();
	qmin.push_back(x);
}

int main()
{
	freopen("window.in","r",stdin);
	freopen("window.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	if(k>n) k=n;
	for(int i=1;i<k;i++) pop(i),pop2(i);
	for(int i=k;i<=n;i++){
		pop(i);
		pop2(i);
		if(!qmax.empty()&&qmax.front()<i-k+1) qmax.pop_front();
		if(!qmin.empty()&&qmin.front()<i-k+1) qmin.pop_front();
		printf("%d ",a[qmin.front()]);
		b[++size]=a[qmax.front()];
	}
	printf("\n");
	for(int i=1;i<=size;i++){
		printf("%d ",b[i]);
	}
	return 0;
}