#include<bits/stdc++.h>
using namespace std;
deque<long long> q;
queue<long long> q1,q2;
long long n,m,t=2,d=-1e9,e=1e9,a,b,c;
long long big=-1,small=1e9,o[1000001];
int main()
{
	cin>>n>>m;
	for(long long i=1;i<=n;i++) cin>>o[i];
	q.push_back(o[1]);
	q.push_back(o[2]);
	while(t!=n)
	{
		d=-1e9;
		e=1e9;
		t++;
		q.push_back(o[t]);
		a=q.front();
		q.pop_front();
		b=q.front();
		q.pop_front();
		c=q.front();
		q.pop_front();
		d=max(a,d);
		d=max(b,d);
		d=max(c,d);
		e=min(a,e);
		e=min(b,e);
		e=min(c,e);
		q.push_front(c);
		q.push_front(b);
		q1.push(e);
		q2.push(d);
	}
	for(long long i=1;i<=n-2;i++)
	{
		cout<<q1.front()<<' ';
		q1.pop();
	}
	cout<<endl;
	for(long long i=1;i<=n-2;i++)
	{
		cout<<q2.front()<<' ';
		q2.pop();
	}
	return 0;
}
P1886