#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int n,cnt=1,Min,Num,T1,T2;
int s[200005],ans[200005];
struct pl{
	int l,r,mi[2],num[2],la,nx,fl,fn,fs;
}e[800005];
void ts(int no){
	if(e[no].fs==1){
		swap(e[no].mi[0],e[no].mi[1]);swap(e[no].num[0],e[no].num[1]);e[e[no].l].fs^=1;e[e[no].r].fs^=1;e[no].fs=0;
	} 
} 
void build(int li,int ri,int no){
	ts(no);
    e[no].fl=e[no].fn=-1;
	if(li==ri){
		e[no].mi[li%2]=s[li];e[no].num[li%2]=li;e[no].mi[(li%2)^1]=1e9;e[no].la=0;e[no].nx=n+1;return;
	}
	e[no].l=++cnt;e[no].r=++cnt;
	int mid=(li+ri)>>1;
	build(li,mid,e[no].l);build(mid+1,ri,e[no].r);
	e[no].num[0]=(e[e[no].l].mi[0]<e[e[no].r].mi[0])?e[e[no].l].num[0]:e[e[no].r].num[0];
	e[no].num[1]=(e[e[no].l].mi[1]<e[e[no].r].mi[1])?e[e[no].l].num[1]:e[e[no].r].num[1];
	e[no].mi[0]=min(e[e[no].l].mi[0],e[e[no].r].mi[0]);
	e[no].mi[1]=min(e[e[no].l].mi[1],e[e[no].r].mi[1]);
}
void find(int li,int ri,int no,int t1,int t2){
	ts(no);
	if(li>t2||ri<t1) return;
	if(li>=t1&&ri<=t2){
		if(e[no].mi[0]<Min) Min=e[no].mi[0],Num=e[no].num[0];return;
	}
	int mid=(li+ri)>>1;
	find(li,mid,e[no].l,t1,t2);find(mid+1,ri,e[no].r,t1,t2);
}
void del(int li,int ri,int no,int mb){
	ts(no);
	if(li>mb||ri<mb) return;
	if(li==ri){
		e[no].mi[0]=e[no].mi[1]=1e9;return;
	}
	int mid=(li+ri)>>1;
	del(li,mid,e[no].l,mb);del(mid+1,ri,e[no].r,mb);
	e[no].num[0]=(e[e[no].l].mi[0]<e[e[no].r].mi[0])?e[e[no].l].num[0]:e[e[no].r].num[0];
	e[no].num[1]=(e[e[no].l].mi[1]<e[e[no].r].mi[1])?e[e[no].l].num[1]:e[e[no].r].num[1];
	e[no].mi[0]=min(e[e[no].l].mi[0],e[e[no].r].mi[0]);
	e[no].mi[1]=min(e[e[no].l].mi[1],e[e[no].r].mi[1]);
}
void change(int li,int ri,int no,int t1,int t2){
	ts(no);
	if(li>t2||ri<t1) return;
	if(li>=t1&&ri<=t2){
		e[no].fs^=1;ts(no);return;
	} 
	int mid=(li+ri)>>1;
	change(li,mid,e[no].l,t1,t2);change(mid+1,ri,e[no].r,t1,t2);
	e[no].num[0]=(e[e[no].l].mi[0]<e[e[no].r].mi[0])?e[e[no].l].num[0]:e[e[no].r].num[0];
	e[no].num[1]=(e[e[no].l].mi[1]<e[e[no].r].mi[1])?e[e[no].l].num[1]:e[e[no].r].num[1];
	e[no].mi[0]=min(e[e[no].l].mi[0],e[e[no].r].mi[0]);
	e[no].mi[1]=min(e[e[no].l].mi[1],e[e[no].r].mi[1]);
}
void tui(int no){
	if(e[no].fl!=-1) e[e[no].l].fl=e[e[no].r].fl=e[no].fl,e[no].la=e[no].fl,e[no].fl=-1;
	if(e[no].fn!=-1) e[e[no].l].fn=e[e[no].r].fn=e[no].fn,e[no].nx=e[no].fn,e[no].fn=-1;
}
void fln(int li,int ri,int no,int mb){
	tui(no);
	if(li>mb||ri<mb) return;
	if(li==ri){
		T1=e[no].la;T2=e[no].nx;return;
	}
	int mid=(li+ri)>>1;
	fln(li,mid,e[no].l,mb);fln(mid+1,ri,e[no].r,mb);
}
void fzl(int li,int ri,int no,int t1,int t2){
	tui(no);
	if(li>t2||ri<t1) return;
	if(li>=t1&&ri<=t2){
		e[no].fl=t1-1;return;
	}
	int mid=(li+ri)>>1;
	fzl(li,mid,e[no].l,t1,t2);fzl(mid+1,ri,e[no].r,t1,t2);
}
void fzn(int li,int ri,int no,int t1,int t2){
	tui(no);
	if(li>t2||ri<t1) return;
	if(li>=t1&&ri<=t2){
		e[no].fn=t2+1;return;
	}
	int mid=(li+ri)>>1;
	fzn(li,mid,e[no].l,t1,t2);fzn(mid+1,ri,e[no].r,t1,t2);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&s[i]);
	build(1,n,1);
	for(int i=1;i<=n/2;i++){
		int de=e[1].num[1];
		int tmp=0;fln(1,n,1,de);
		ans[2*i-1]=e[1].mi[1];Min=1e9+1;Num=0;find(1,n,1,de+1,T2-1);
		ans[2*i]=Min;del(1,n,1,de);del(1,n,1,Num);change(1,n,1,de+1,Num-1);
        fzn(1,n,1,T1+1,de-1);fzn(1,n,1,de+1,Num-1);
        fzl(1,n,1,de+1,Num-1);fzl(1,n,1,Num+1,T2-1);
	}
	for(int i=1;i<n;i++) printf("%d ",ans[i]);
	printf("%d\n",ans[n]);
	return 0;
}


Measured memory_bytes: 23040