#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
int p[222222],a[111111],b[111111],n,ans[222222],l,r,cnt,id,ppp;
pair<int,int> odd[444444],even[444444];
set<pair<int,int> > s;
struct qj
{
	int l,r,mnl,mnr;
	bool type;
}jc[666666],q1,q2,q3;
qj make(int l,int r,int mnl,int mnr,bool type)
{
	qj a;
	a.l=l;a.r=r;a.mnl=mnl;a.mnr=mnr;a.type=type;
	return a;
}
void builda(int l,int r,int node)
{
	if (l==r) odd[node]=make_pair(a[l],l);
	else
	{
		int mid=(l+r)/2;
		builda(l,mid,node*2);
		builda(mid+1,r,node*2+1);
		odd[node]=min(odd[node*2],odd[node*2+1]);
	}
}
void buildb(int l,int r,int node)
{
	if (l==r) even[node]=make_pair(b[l],l);
	else
	{
		int mid=(l+r)/2;
		buildb(l,mid,node*2);
		buildb(mid+1,r,node*2+1);
		even[node]=min(even[node*2],even[node*2+1]);
	}
}
pair<int,int> querya(int beg,int en,int l,int r,int node)
{
	if (l>en || r<beg) return make_pair(1e9,1e9);
	if (l>=beg && r<=en) return odd[node];
	int mid=(l+r)/2;
	return min(querya(beg,en,l,mid,node*2),querya(beg,en,mid+1,r,node*2+1));
}
pair<int,int> queryb(int beg,int en,int l,int r,int node)
{
	if (l>en || r<beg) return make_pair(1e9,1e9);
	if (l>=beg && r<=en) return even[node];
	int mid=(l+r)/2;
	return min(queryb(beg,en,l,mid,node*2),queryb(beg,en,mid+1,r,node*2+1));
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&p[i]);
	for (int i=1;i<=n;i++)
	{
		if (i&1) a[(i+1)/2]=p[i];
		else b[i/2]=p[i];
	}
	builda(1,n/2,1);
	buildb(1,n/2,1);
	l=querya(1,n/2,1,n/2,1).second;
	r=queryb(l,n/2,1,n/2,1).second;
	cnt=1;jc[1]=make(1,n,l*2-1,r*2,0);
	s.insert(make_pair(a[l],1));
	for (int i=1;i<=n/2;i++)
	{
		set<pair<int,int> >::iterator it=s.begin();
		id=it->second;
		s.erase(it);
		ans[++ppp]=p[jc[id].mnl];
		ans[++ppp]=p[jc[id].mnr];
		if (jc[id].type==0)
		{
			if (jc[id].l<jc[id].mnl-1)
			{
				l=querya(jc[id].l/2+1,jc[id].mnl/2,1,n/2,1).second;
				r=queryb(l,jc[id].mnl/2,1,n/2,1).second;
				q1=make(jc[id].l,jc[id].mnl-1,l*2-1,r*2,0);
				jc[++cnt]=q1;
				s.insert(make_pair(p[l*2-1],cnt));
			}
			if (jc[id].mnr+1<jc[id].r)
			{
				l=querya(jc[id].mnr/2+1,jc[id].r/2,1,n/2,1).second;
				r=queryb(l,jc[id].r/2,1,n/2,1).second;
				q3=make(jc[id].mnr+1,jc[id].r,l*2-1,r*2,0);
				jc[++cnt]=q3;
				s.insert(make_pair(p[l*2-1],cnt));
			}
			if (jc[id].mnl+1<jc[id].mnr-1)
			{
				l=queryb(jc[id].mnl/2+1,jc[id].mnr/2-1,1,n/2,1).second;
				r=querya(l+1,jc[id].mnr/2,1,n/2,1).second;
				q2=make(jc[id].mnl+1,jc[id].mnr-1,l*2,r*2-1,1);
				jc[++cnt]=q2;
				s.insert(make_pair(p[l*2],cnt));
			}
		}
		else
		{
			if (jc[id].l<jc[id].mnl-1)
			{
				l=queryb(jc[id].l/2,jc[id].mnl/2-1,1,n/2,1).second;
				r=querya(l+1,jc[id].mnl/2,1,n/2,1).second;
				q1=make(jc[id].l,jc[id].mnl-1,l*2,r*2-1,1);
				jc[++cnt]=q1;
				s.insert(make_pair(p[l*2],cnt));
			}
			if (jc[id].mnr+1<jc[id].r)
			{
				l=queryb(jc[id].mnr/2+1,jc[id].r/2,1,n/2,1).second;
				r=querya(l+1,jc[id].r/2+1,1,n/2,1).second;
				q3=make(jc[id].mnr+1,jc[id].r,l*2,r*2-1,1);
				jc[++cnt]=q3;
				s.insert(make_pair(p[l*2],cnt));
			}
			if (jc[id].mnl+1<jc[id].mnr-1)
			{
				l=querya(jc[id].mnl/2+1,jc[id].mnr/2,1,n/2,1).second;
				r=queryb(l,jc[id].mnr/2,1,n/2,1).second;
				q2=make(jc[id].mnl+1,jc[id].mnr-1,l*2-1,r*2,0);
				jc[++cnt]=q2;
				s.insert(make_pair(p[l*2-1],cnt));
			}
		}
	}
	for (int i=1;i<=n;i++) printf("%d ",ans[i]);
	printf("\n");
	return 0;
}

Measured memory_bytes: 15616