#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<queue>
#include<math.h>
#include<complex>

using namespace std;
long long int num[200005],h,w,n,x[200001],y[200001],res=9999999,can=0,now=1;

const long long int INF=1145141919810931;
const long long int MAX_TREE=1024*256;
//区間[left,right),valueは値
struct TREE{
	long long int left,right,value;
};
TREE odd[MAX_TREE];
TREE even[MAX_TREE];
//2^20
//区間は1-indexed

void Segment_Tree_LR_Set(long long int l,long long int r,long long int id){
	odd[id].left=l;
	odd[id].right=r;
	if(id*2<MAX_TREE){Segment_Tree_LR_Set(l, (l+r)/2, id*2);Segment_Tree_LR_Set((l+r)/2, r, id*2+1);}
}

void Segment_Tree_Change_Loop(long long int id)
{
	if(id==0){return;}
	odd[id].value=min(odd[id*2].value,odd[id*2+1].value);
	
	Segment_Tree_Change_Loop(id/2);
}

void Segment_Tree_Change(long long int id,long long int num){
	odd[id+MAX_TREE/2-1].value=num;
	Segment_Tree_Change_Loop((id+MAX_TREE/2-1)/2);
}

long long int Segment_Tree_Check(long long int l,long long int r,long long int id){
		//cout<<id<<" "<<l<<" "<<r<<endl;
		if(odd[id].left>=r||odd[id].right<=l||r<=l){return INF;}
		else if(l==odd[id].left&&r==odd[id].right){return odd[id].value;}
		else {return min(Segment_Tree_Check(l,min(r,odd[2*id].right),2*id),Segment_Tree_Check(max(l,odd[2*id+1].left), r, 2*id+1));}
		
}



void Segment_Tree_LR_Set2(long long int l,long long int r,long long int id){
	even[id].left=l;
	even[id].right=r;
	if(id*2<MAX_TREE){Segment_Tree_LR_Set2(l, (l+r)/2, id*2);Segment_Tree_LR_Set2((l+r)/2, r, id*2+1);}
}

void Segment_Tree_Change_Loop2(long long int id)
{
	if(id==0){return;}
	even[id].value=min(even[id*2].value,even[id*2+1].value);
	
	Segment_Tree_Change_Loop2(id/2);
}

void Segment_Tree_Change2(long long int id,long long int num){
	even[id+MAX_TREE/2-1].value=num;
	Segment_Tree_Change_Loop2((id+MAX_TREE/2-1)/2);
}

long long int Segment_Tree_Check2(long long int l,long long int r,long long int id){
		//cout<<id<<" "<<l<<" "<<r<<endl;
		if(even[id].left>=r||even[id].right<=l||r<=l){return INF;}
		else if(l==even[id].left&&r==even[id].right){return even[id].value;}
		else {return min(Segment_Tree_Check2(l,min(r,even[2*id].right),2*id),Segment_Tree_Check2(max(l,even[2*id+1].left), r, 2*id+1));}
		
}



const long long int mod=1000000007;

typedef pair<long long int,long long int> P;
priority_queue<pair<long long int,P> ,vector<pair<long long int,P> > ,greater<pair<long long int,P> > > q;

int main(){
	cout << fixed << setprecision(18);
	string str,tmp;
	cin>>n;
	
	for(int i=1;i<=n;i++){
		cin>>num[i];	
	}
	
	Segment_Tree_LR_Set(1, MAX_TREE/2+1, 1);
	Segment_Tree_LR_Set2(1, MAX_TREE/2+1, 1);
	for(int i=1;i<MAX_TREE;i++)
	{
		odd[i].value=INF;
		even[i].value=INF;
	}
	for(int i=1;i<=n;i++){
		if(i%2==1){
			Segment_Tree_Change((i+1)/2, num[i]);
		}else{
			Segment_Tree_Change2(i/2,num[i]);	
		}
	}
	
	q.push({Segment_Tree_Check(1, n/2+1, 1),{1,n}});
	while(!q.empty()){
		long long int l,r;
		long long int first=q.top().second.first,second=q.top().second.second; 
		
		q.pop();
		if(first%2==1){
			l=(first+1)/2,r=second/2;
			
			long long int ok=r+1+1,ng=l-1;
			long long int mi=Segment_Tree_Check(l, r+1, 1);
			while(ok-ng>1){
				long long int mid=(ok+ng)/2;
				if(mi!=Segment_Tree_Check(l, mid+1, 1)){
					ng=mid;	
				}else{
					ok=mid;	
				}
			}
			
			
			if(first<ng*2){
				q.push({Segment_Tree_Check(l, ng+1, 1),{first,ng*2}});	
				//cout<<"A"<<q.top().second.first<<" "<<ng*2<<endl;
				//cout<<Segment_Tree_Check(l, ng+1, 1)<<endl;
			}
			long long int memor=ok;
			
			long long int memo=mi;
			l=ok;
			ok=r+1+1;
			ng=l-1;
			mi=Segment_Tree_Check2(l, r+1, 1);
			
			while(ok-ng>1){
				long long int mid=(ok+ng)/2;
				if(mi!=Segment_Tree_Check2(l, mid+1, 1)){
					ng=mid;	
				}else{
					ok=mid;	
				}
			}
			
			if(l*2<ng*2+1){
				
				q.push({Segment_Tree_Check2(l, ng+1, 1),{l*2,ng*2+1}});
				//cout<<l*2<<ng*2+1<<endl;
				//cout<<Segment_Tree_Check2(l, ng+1, 1);
			}
			
			if(ok*2+1<second){
			
				q.push({Segment_Tree_Check(ok+1, r+1, 1),{ok*2+1,second}});
				//cout<<"C";
			}
			
			
			cout<<memo<<" "<<mi<<" ";
			
			
		}else
		{
			l=first/2;
			r=(second-1)/2;
			
			long long int ok=r+1+1,ng=l-1;
			long long int mi=Segment_Tree_Check2(l, r+1, 1);
			while(ok-ng>1){
				long long int mid=(ok+ng)/2;
				if(mi!=Segment_Tree_Check2(l, mid+1, 1)){
					ng=mid;	
				}else{
					ok=mid;	
				}
			}
			
			if(first<ng*2+1){
				q.push({Segment_Tree_Check2(l, ng+1, 1),{first,ng*2+1}});	
			}
			long long int memor=ok;
			
			long long int memo=mi;
			l=ok+1;
			r=(second+1)/2;
			ok=r+1+1;
			ng=l-1;
			mi=Segment_Tree_Check(l, r+1, 1);
			
			while(ok-ng>1){
				long long int mid=(ok+ng)/2;
				if(mi!=Segment_Tree_Check(l, mid+1, 1)){
					ng=mid;	
				}else{
					ok=mid;	
				}
			}
			
			if(l*2-1<ng*2){
				
				q.push({Segment_Tree_Check(l, ng+1, 1),{l*2-1,ng*2}});
			}
			
			if(ok*2<second){
			
				q.push({Segment_Tree_Check2(ok, r, 1),{ok*2,second}});
			}
			
			
			
			cout<<memo<<" "<<mi<<" ";
			
			
		}
		
	}
	
}


Measured memory_bytes: 19572