#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 2e5 + 5;

template<typename temp_type> struct segment_tree {
	// Elements count
	int n;
	
	// Values
	int vals[MAXN];
	
	// Tree
	temp_type tt[4 * MAXN];
	
	// Combine from two values
	temp_type combine(temp_type v1, temp_type v2){
		return (vals[v1] < vals[v2] ? v1 : v2);
	}
	
	// Recursive build
	void build(int ind, int tl, int tr){
		if (tl == tr){
			//tt[ind] = vals[tl];
			tt[ind] = tl;
			return;
		}
		int tm = (tl + tr) >> 1;
		build(ind << 1, tl, tm);
		build((ind << 1) + 1, tm + 1, tr);
		tt[ind] = combine(tt[ind << 1], tt[(ind << 1) + 1]);
	}	
	
	// Recursive get
	temp_type get_val(int ind, int tl, int tr, int l, int r){
		if (tl == l && tr == r){
			return tt[ind];
		}
		int tm = (tl + tr) >> 1;
		if (r <= tm){
			return get_val(ind << 1, tl, tm, l, r);
		} else if (l > tm){
			return get_val((ind << 1) + 1, tm + 1, tr, l, r);
		} else {
			return combine(get_val(ind << 1, tl, tm, l, tm), get_val((ind << 1) + 1, tm + 1, tr, tm + 1, r));
		}
	}	
	
	// Build (for call)
	void build(){
		build(1, 0, n - 1);
	}
	
	// Get (for call)
	temp_type get_val(int l, int r){
		return get_val(1, 0, n - 1, l, r);
	}
};

segment_tree<int> tt_0, tt_1;

int per[MAXN];

int ans[MAXN], top_ans;

vi g[MAXN];
int top_g;

pii v[MAXN];

void rec_get_g(int l, int r, int prv){
	if (l > r){
		return;
	}
	int ind1, ind2;
	if (l & 1){
		ind1 = tt_1.get_val(l, r);
		ind2 = tt_0.get_val(ind1 + 1, r);
	} else {
		ind1 = tt_0.get_val(l, r);
		ind2 = tt_1.get_val(ind1 + 1, r);
	}
	v[top_g] = mp(per[ind1], per[ind2]);
	if (prv != -1){
		g[prv].pb(top_g);
	}
	int cur = top_g;
	top_g++;
	rec_get_g(l, ind1 - 1, cur);
	rec_get_g(ind1 + 1, ind2 - 1, cur);
	rec_get_g(ind2 + 1, r, cur);
}

set<pair<pii, int> > st;

void bfs(){
	top_ans = 0;
	st.insert(mp(v[0], 0));
	while(!st.empty()){
		int ind = st.begin()->_2;
		st.erase(st.begin());
		ans[top_ans++] = v[ind]._1;
		ans[top_ans++] = v[ind]._2;
		REP(i, 0, SZ(g[ind])){
			int to = g[ind][i];
			st.insert(mp(v[to], to));
		}
	}
}

void solve(){
	int n;
	scanf("%d", &n);
	REP(i, 0, n){
		scanf("%d", &per[i]);
		if (i & 1){
			tt_0.vals[i] = INF;
			tt_1.vals[i] = per[i];
		} else {
			tt_0.vals[i] = per[i];
			tt_1.vals[i] = INF;
		}
	}
	tt_0.n = tt_1.n = n;
	tt_0.build();
	tt_1.build();
	top_g = 0;
	rec_get_g(0, n - 1, -1);
	bfs();
	REP(i, 0, n){
		printf("%d ", ans[i]);
	}
	putchar('\n');
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 32512