#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;

/*
*/

//値が最小となる場所のidを返す
struct segment_tree{
	typedef struct node_{
		mp smallest;
		int left,right; //[left,right)
		struct node_ *left_child,*right_child;
	}* node;
	node parent_node = new node_;
	segment_tree(){};
	mp eval(mp a,mp b){//ふさわしい方を返す評価関数（ここでは第１要素が小さい方）
		if(a.first<b.first){
			return a;
		}else{
			return b;
		}
	}
	void make_segtree_min(int l,int r,mp *a){
		make_segtree_node_min(parent_node,l,r,a);
	}
	mp make_segtree_node_min(node p,int left,int right,mp *a){
		p->left=left;
		p->right=right;
		if(left+1!=right){
			node q=new node_,r=new node_;
			p->left_child=q;
			p->right_child=r;
			p->smallest=eval( make_segtree_node_min(q,left,(left+right)/2,a), make_segtree_node_min(r,(left+right)/2,right,a) );
		}else{//要素数が1個
			p->left_child=NULL;
			p->right_child=NULL;
			p->smallest=a[left];
		}
		return p->smallest;
	}
	mp range_min(int left,int right){
		return range_min_node(parent_node,left,right);
	}
	mp range_min_node(node p,int left,int right){
		if(p->right<=left || right<=p->left)return make_pair(LLONG_MAX,-1);
		if(left<=p->left && p->right<=right)return p->smallest;
		return eval( range_min_node(p->left_child,left,right), range_min_node(p->right_child,left,right) );
	}
};

struct range{
	ll v,pos,l,r;
	bool operator>(const range &s) const{
		return v > s.v;
	}
};

int main(void){
	ll n;
	mp ev[200010],od[200010];
	segment_tree even,odd;//first=値，second=pos
	priority_queue<range,vector<range>,greater<range>> Q;
	string ans="";
	cin>>n;
	rep(i,n/2){
		ll x,y;
		cin>>x>>y;
		ev[i*2]=make_pair(x,i*2);
		ev[i*2+1]=make_pair(LLONG_MAX,i*2+1);//奇数は選ばない
		od[i*2]=make_pair(LLONG_MAX,i*2);//偶数は選ばない
		od[i*2+1]=make_pair(y,i*2+1);
	}
	even.make_segtree_min(0,n,ev);
	odd.make_segtree_min(0,n,od);
	//
	mp tmp = even.range_min(0,n);
	Q.push({tmp.first,tmp.second,0,n});//最初に全区間を入れる
	while(!Q.empty()){
		range parent_range=Q.top();Q.pop();
		if(parent_range.l+2==parent_range.r){//定数倍の高速化
			ans+=to_string(parent_range.v)+" "+to_string(min(ev[parent_range.pos+1].first,od[parent_range.pos+1].first))+" ";
			continue;
		}
		//左端と同じmod，違うmodの順に区間を分割する
		if(parent_range.l%2==0){
			if(parent_range.pos!=parent_range.l){//左があるか
				mp a = even.range_min(parent_range.l,parent_range.pos);
				Q.push({a.first,a.second,parent_range.l,parent_range.pos});
			}
			mp a = odd.range_min(parent_range.pos+1,parent_range.r);
			if(parent_range.pos+1!=a.second){//真ん中があるか
				mp b = odd.range_min(parent_range.pos+1,a.second);
				Q.push({b.first,b.second,parent_range.pos+1,a.second});
			}
			if(parent_range.r!=a.second+1){//右があるか
				mp b = even.range_min(a.second+1,parent_range.r);
				Q.push({b.first,b.second,a.second+1,parent_range.r});
			}
			ans+=to_string(parent_range.v)+" "+to_string(a.first)+" ";
		}else{
			if(parent_range.pos!=parent_range.l){//左があるか
				mp a = odd.range_min(parent_range.l,parent_range.pos);
				Q.push({a.first,a.second,parent_range.l,parent_range.pos});
			}
			mp a = even.range_min(parent_range.pos+1,parent_range.r);
			if(parent_range.pos+1!=a.second){//真ん中があるか
				mp b = even.range_min(parent_range.pos+1,a.second);
				Q.push({b.first,b.second,parent_range.pos+1,a.second});
			}
			if(parent_range.r!=a.second+1){//右があるか
				mp b = odd.range_min(a.second+1,parent_range.r);
				Q.push({b.first,b.second,a.second+1,parent_range.r});
			}
			ans+=to_string(parent_range.v)+" "+to_string(a.first)+" ";
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 48432