#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200010;
int n,cnt,tot=1,a[N],b[N],vis[N],rt[N*6],f[N],ch[N][2],val[N],siz[N],mini[N],minid[N],idx[N],tag[N],root[N],pos[N],tr0[N*4],tr1[N*4],sz[N*4];
void maintain(int o){
	siz[o]=siz[ch[o][0]]+siz[ch[o][1]]+1;
	mini[o]=val[o],minid[o]=o;
	if(ch[o][0]&&mini[o]>mini[ch[o][0]]){
		mini[o]=mini[ch[o][0]];
		minid[o]=minid[ch[o][0]];
	}
	if(ch[o][1]&&mini[o]>mini[ch[o][1]]){
		mini[o]=mini[ch[o][1]];
		minid[o]=minid[ch[o][1]];
	}
	return;
}
int which(int x){
	return ch[f[x]][1]==x;
}
void rotate(int x){
	int fx=f[x],ffx=f[f[x]];
	int d=which(x),fd=which(fx);
	f[x]=ffx;
	if(ffx)
		ch[ffx][fd]=x;
	ch[fx][d]=ch[x][d^1];
	f[ch[x][d^1]]=fx;
	ch[x][d^1]=fx;
	f[fx]=x;
	maintain(fx);
	maintain(x);
	return;
}
void pushdown(int o){
	if(ch[o][0])
		root[ch[o][0]]=tag[ch[o][0]]=tag[o];
	if(ch[o][1])
		root[ch[o][1]]=tag[ch[o][1]]=tag[o];
	return;
}
void push(int x){
	if(!x)
		return;
	push(f[x]);
	pushdown(x);
	return;
}
void splay(int x,int t){
	push(x);
	while(f[x]!=t){
		int fx=f[x];
		if(f[fx]!=t){
			if(which(fx)==which(x))
				rotate(fx);
			else rotate(x);
		}
		rotate(x);
	}
	return;
}
void build(int &o,int l,int r,int *a,int t){
	if(l>r)
		return;
	o=++cnt;
	int mid=(l+r)>>1;
	val[o]=a[mid];
	idx[a[mid]]=o;
	root[o]=tag[o]=t;
	build(ch[o][0],l,mid-1,a,t);
	build(ch[o][1],mid+1,r,a,t);
	f[ch[o][0]]=o;
	f[ch[o][1]]=o;
	maintain(o);
	return;
}
int find(int o,int x){
	if(x==siz[ch[o][0]]+1)
		return o;
	if(x<=siz[ch[o][0]])
		return find(ch[o][0],x);
	return find(ch[o][1],x-siz[ch[o][0]]-1);
}
void push_up(int o){
	if(sz[o<<1]&1){
		tr0[o]=min(tr0[o<<1],tr1[o<<1|1]);
		tr1[o]=min(tr1[o<<1],tr0[o<<1|1]);
	}
	else{
		tr0[o]=min(tr0[o<<1],tr0[o<<1|1]);
		tr1[o]=min(tr1[o<<1],tr1[o<<1|1]);
	}
	sz[o]=sz[o<<1]+sz[o<<1|1];
	return;
}
void buildseg(int o,int l,int r){
	if(l==r){
		sz[o]=1;
		tr0[o]=a[l];
		tr1[o]=0x7f7f7f7f;
		return;
	}
	int mid=(l+r)>>1;
	buildseg(o<<1,l,mid);
	buildseg(o<<1|1,mid+1,r);
	push_up(o);
	return;
}
void remove(int o,int l,int r,int x){
	if(l==r){
		sz[o]=0;
		tr0[o]=0x7f7f7f7f;
		tr1[o]=0x7f7f7f7f;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
		remove(o<<1,l,mid,x);
	if(x>mid)
		remove(o<<1|1,mid+1,r,x);
	push_up(o);
	return;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i+i<=n;i++)
		scanf("%d%d",a+i,b+i);
	build(rt[0],1,n>>1,a,0);
	build(rt[1],1,n>>1,b,1);
	for(int i=n-1;i>=1;i-=2)
		a[i]=a[i/2+1];
	for(int i=2;i<=n;i+=2)
		a[i]=b[i/2];
	for(int i=1;i<=n;i++)
		pos[a[i]]=i;
	buildseg(1,1,n);
	for(int j=1;j<=n/2;j++){
		int i=tr0[1];
		int y=idx[i];
		splay(y,0);
		rt[root[y]]=y;
		vis[i]=1;
		printf("%d ",i);
		remove(1,1,n,pos[i]);
		int x=find(rt[root[y]^1],siz[ch[y][0]]+1);
		splay(x,0);
		rt[root[y]^1]=x;
		if(!ch[x][1]||val[x]<mini[ch[x][1]]){
			vis[val[x]]=1;
			printf("%d ",val[x]);
			remove(1,1,n,pos[val[x]]);
			root[ch[y][0]]=tag[ch[y][0]]=++tot;
			rt[tot]=ch[y][0];
			f[ch[y][0]]=0;
			ch[y][0]=0;
			root[ch[x][0]]=tag[ch[x][0]]=++tot;
			rt[tot]=ch[x][0];
			f[ch[x][0]]=0;
			ch[x][0]=0;
			root[ch[y][1]]=tag[ch[y][1]]=++tot;
			rt[tot]=ch[y][1];
			f[ch[y][1]]=0;
			ch[y][1]=0;
			root[ch[x][1]]=tag[ch[x][1]]=++tot;
			rt[tot]=ch[x][1];
			f[ch[x][1]]=0;
			ch[x][1]=0;
		}
		else{
			vis[mini[ch[x][1]]]=1;
			printf("%d ",mini[ch[x][1]]);
			remove(1,1,n,pos[mini[ch[x][1]]]);
			int z=minid[ch[x][1]];
			splay(z,0);
			rt[root[z]]=z;
			splay(x,z);
			int w=find(rt[root[y]],siz[ch[z][0]]+1);
			splay(w,y);
			root[ch[w][1]]=tag[ch[w][1]]=++tot;
			rt[tot]=ch[w][1];
			f[ch[w][1]]=0;
			ch[w][1]=0;
			root[ch[z][1]]=tag[ch[z][1]]=++tot;
			rt[tot]=ch[z][1];
			f[ch[z][1]]=0;
			ch[z][1]=0;
			root[ch[y][0]]=tag[ch[y][0]]=++tot;
			rt[tot]=ch[y][0];
			f[ch[y][0]]=0;
			ch[y][0]=0;
			root[ch[x][0]]=tag[ch[x][0]]=++tot;
			rt[tot]=ch[x][0];
			f[ch[x][0]]=0;
			ch[x][0]=0;
			root[ch[z][0]]=tag[ch[z][0]]=++tot;
			rt[tot]=ch[z][0];
			f[ch[z][0]]=0;
			ch[z][0]=0;
			root[ch[y][1]]=tag[ch[y][1]]=++tot;
			rt[tot]=ch[y][1];
			f[ch[y][1]]=0;
			ch[y][1]=0;
		}
	}
	return 0;
}

Measured memory_bytes: 22152