#include<bits/stdc++.h>
using namespace std;
 
long long N;
long long p[200005];
 
#define INF 1e9
 
/*
 *範囲のminimumを取得
 */
//区間[l, r)
struct segtree {
	vector<long long> data;
	long long n;
	segtree(long long nin){
		n = pow( 2, ceil( log(nin) / log(2) ) );
		long long size = 2 * n - 1;
		this->data.resize(size, 1e9);
	}
 
	//API for update val
	void update(long long idx, long long val){
		update(idx, val, 0, 0, n);
	}
 
	long long update(long long idx, long long val, long long node_id, long long left, long long right){
		//if query idx is within range return val
		if( !( left <= idx && idx < right ) ){
			return data[node_id];
		}
		if( left + 1 < right ) {
			//when node range is not 1, get update children val and update node data
			long long mid = (left + right) / 2 ;
			long long L = update(idx, val, 2 * node_id + 1, left, mid);
			long long R = update(idx, val, 2 * node_id + 2, mid, right);
			data[node_id] = min(L, R);
		} else {
			//when node range is 1, update node data
			data[node_id] = min(data[node_id], val);
		}
		return data[node_id];
	}
	
	//API for get value of [l, r)
	long long get(long long l, long long r){
		return get(l, r, 0, 0, n);
	}
 
	/*
	 *internaly used function
	 *query_l: query left range
	 *query_r: query right range
	 *node_id: node id of 
	 *node_l:  node left range 
	 *node_r:  node right range
	 */
	long long get(long long query_l, long long query_r, long long node_id, long long node_l, long long node_r){
		//query range is outside of node range: return INF
		if( query_r <= node_l || node_r <= query_l ){
			return INF;
		}
		//query range is within node range: return node val
		if( query_l <= node_l && node_r <= query_r ){
			return data[node_id];
		}
		long long mid = (node_l + node_r) / 2;
		long long L = get(query_l, query_r, 2 * node_id + 1, node_l, mid);
		long long R = get(query_l, query_r, 2 * node_id + 2, mid, node_r);
		return min(L, R);
	}
};
 
 
int main(){
	cin >> N;
	segtree oddsg(N);
	segtree evensg(N);
	for(long long i = 0; i < N; i++){
		long long tmp;
		cin >> tmp;
		p[tmp] = i;
 
		if(i%2 == 0){
			evensg.update(i, tmp);
		}else{
			oddsg.update(i, tmp);
		}
	}
 
	deque<long long> ans;
	//                     fval  ,          head,   tail
	priority_queue<pair<long long, pair<long long, long long> >,
		vector<pair<long long, pair<long long, long long> > >,
		greater<pair<long long, pair<long long, long long> > > >Q;

	Q.push(make_pair(evensg.get(0, N), make_pair(0, N)));

	while(!Q.empty()){
		long long head = Q.top().second.first;
		long long tail = Q.top().second.second;
		long long memotail = tail;
		Q.pop();
		if(head + 1 >= tail){
			continue;
		}

		if((tail - head)%2 != 0){
			return 1;
		}

		long long fpos;
		long long fval;
		long long spos;
		long long sval;

		if(head % 2 == 0){
			fval = evensg.get(head, tail);
			fpos = p[fval];
			sval = oddsg.get(fpos + 1, tail);
			spos = p[sval];
		}else{
			fval = oddsg.get(head, tail);
			fpos = p[fval];
			sval = evensg.get(fpos + 1, tail);
			spos = p[sval];
		}
		
		if(fval == INF || sval == INF){
			return 1;
		}

		ans.push_back(fval);
		ans.push_back(sval);

		head = head;
		tail = fpos;
		if(head % 2 == 0){
			fval = evensg.get(head, tail);
		}else{
			fval = oddsg.get(head, tail);
		}
		Q.push(make_pair(fval, make_pair(head, tail)));


		head = fpos + 1;
		tail = spos;
		if(head % 2 == 0){
			fval = evensg.get(head, tail);
		}else{
			fval = oddsg.get(head, tail);
		}
		Q.push(make_pair(fval, make_pair(head, tail)));


		head = spos + 1;
		tail = memotail;
		if(head % 2 == 0){
			fval = evensg.get(head, tail);
		}else{
			fval = oddsg.get(head, tail);
		}
		Q.push(make_pair(fval, make_pair(head, tail)));
	}

	for(int i = 0; i < ans.size(); i++){
		cout << ans[i];
		if(i != ans.size() - 1){
			cout << " ";
		}
	}
	cout << endl;
}


Measured memory_bytes: 19088