#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
#define pb push_back

template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 998244353;
constexpr int inf = 3e18;

template<typename Monoid,typename OperatorMonoid,typename F,typename G,typename H>
struct Segtree{
	int size=1;
	vector<Monoid>dat;
	vector<OperatorMonoid>lazy;
	const F f;
	const G g;
	const H h;
	Monoid M;
	OperatorMonoid OM;
	void set(int a,Monoid x){
		dat[a+size-1]=x;
	}
	void init(){
		for(int i=size-2;i>=0;i--){
			dat[i]=f(dat[i*2+1],dat[i*2+2]);
		}
	}
	void eval(int k,int l,int r){
		if(lazy[k]!=OM){
			dat[k]=g(dat[k],lazy[k],(r-l));
			if(r-l>1){
				lazy[2*k+1]=h(lazy[2*k+1],lazy[k]);
				lazy[2*k+2]=h(lazy[2*k+2],lazy[k]);
			}
			lazy[k]=OM;
		}
	}
	void update(int a,int b,OperatorMonoid M,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l)return;
		if(a<=l&&r<=b){
			lazy[k]=h(lazy[k],M);
			eval(k,l,r);
			return;
		}
		update(a,b,M,k*2+1,l,(l+r)/2);
		update(a,b,M,k*2+2,(l+r)/2,r);
		dat[k]=f(dat[k*2+1],dat[k*2+2]);
	}
	Monoid query(int a,int b,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l)return M;
		if(a<=l&&r<=b)return dat[k];
		Monoid lv=query(a,b,k*2+1,l,(l+r)/2);
		Monoid rv=query(a,b,k*2+2,(l+r)/2,r);
		return f(lv,rv);
	}
	Segtree(int x,F f,G g,H h,Monoid M,OperatorMonoid OM)
	:f(f),g(g),h(h),M(M),OM(OM){
		while(size<x)size*=2;
		dat.resize(size*2-1,M);
		lazy.resize(size*2-1,OM);
	}
};
int N,A[200005];
set<int>used;
signed main(){
	cin>>N;
	auto f=[](P a,P b){
		if(a.first<b.first)return a;
		return b;
	};
	auto g=[](P a,int b,int sz){
		return P(b,a.second);
	};
	auto h=[](int a,int b){return b;};
	Segtree<P,int,decltype(f),decltype(g),decltype(h)>seg1(N,f,g,h,{inf,inf},inf-1),
			seg2(N,f,g,h,{inf,inf},inf-1);
	rep(i,N){
		cin>>A[i];
		if(i%2==0)seg1.set(i,{A[i],i});
		else seg2.set(i,{A[i],i});
	}
	seg1.init();seg2.init();
	used.insert(N);used.insert(0);
	priority_queue<P,vector<P>,greater<P>>que;
	que.push({seg1.query(0,seg1.size).first,0});
	while(!que.empty()){
		P p=que.top();que.pop();
		int le=p.second;
		int ri=*used.upper_bound(p.second);
		P q;
		if(le%2){
			p=seg2.query(p.second,ri);
			q=seg1.query(p.second,ri);
		}else {
			p=seg1.query(p.second,ri);
			q=seg2.query(p.second,ri);
		}
		cout<<p.first<<" "<<q.first<<" ";
		if(p.second!=le){
			if(le%2)que.push({seg2.query(le,p.second).first,le});
			else que.push({seg1.query(le,p.second).first,le});
		}
		if(q.second-p.second>1){
			if(le%2)que.push({seg1.query(p.second+1,q.second).first,p.second+1});
			else que.push({seg2.query(p.second+1,q.second).first,p.second+1});
		}
		if(q.second!=ri-1){
			if(le%2)que.push({seg2.query(q.second,ri).first,q.second+1});
			else que.push({seg1.query(q.second,ri).first,q.second+1});
		}
		used.insert(p.second);used.insert(q.second);
	}
	cout<<endl;
}


Measured memory_bytes: 39304