#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
using namespace std;
int n;
int a[200010];
int ind[200010];
vector<int>ans;
set<int>st;
set<int>bar;
int mnum;
struct segment_tree{
	int mn[1<<20],N,sz;
	void init()
	{
		N=1;
		while(N<n)N*=2;
		for(int i=0;i<N*2-1;i++)mn[i]=1e9;
	}
	void pushup(int x)
	{
		while(x>0)
		{
			x=(x-1)>>1;
			mn[x]=min(mn[(x<<1)+1],mn[(x<<1)+2]);
		}
	}
	void ins(int x)
	{
		int pos=(sz++)+N-1;
		mn[pos]=x;
		pushup(pos);
	}
	int query(int a,int b,int k,int l,int r)
	{
		if(a>=r || b<=l)return 1e9;
		if(a<=l && b>=r)return mn[k];
		return min(query(a,b,(k<<1)+1,l,(l+r)>>1),query(a,b,(k<<1)+2,(l+r)>>1,r));
	}
}s[2];
int main()
{
	scanf("%d",&n);
	s[0].init();
	s[1].init();
	for(int i=1;i<=n;i++)
	{
		scanf("%d",a+i);
		ind[a[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		s[i&1].ins(a[i]);
		s[(i&1)^1].ins(1e9);
	}
	st.insert(s[1].query(0,n-1,0,0,s[1].N));
	bar.insert(0);
	bar.insert(n+1);
	int l=0; 
	while(l<n)
	{
		mnum=*st.begin();
		ans.push_back(mnum);
		int w=ind[mnum];
		int mnn=1e9;
		set<int>::iterator it1=bar.lower_bound(w);
		set<int>::iterator it2=it1;
		it1--;
		mnn=min(mnn,s[(w&1)^1].query(w,(*it2)-1,0,0,s[(w&1)^1].N));
		ans.push_back(mnn);
		st.erase(st.begin());
		int tt=s[w&1].query((*it1),w-1,0,0,s[w&1].N);
		if(tt!=1e9)st.insert(tt);
		tt=s[(w&1)^1].query(w,ind[mnn]-1,0,0,s[(w&1)^1].N);
		if(tt!=1e9)st.insert(tt);
		tt=s[w&1].query(ind[mnn],(*it2)-1,0,0,s[w&1].N);
		if(tt!=1e9)st.insert(tt);
		bar.insert(w);
		bar.insert(ind[mnn]);
		l+=2;
	}
	for(int i=0;i<n;i++)printf("%d ",ans[i]);
	return 0;
}