#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

#define DEBUG_MODE
#ifdef DEBUG_MODE
#define dump(x) cout << #x << " : " << x << endl
#define LINE cout << "line : " << __LINE__ << endl
#define dumpV(v) cout << #v << " : ["; for(auto& t : v) cout << t << ", "; cout<<"]" << endl
#define STOP assert(false)
#else
#define dump(x) ;
#define LINE 	;
#define dumpV(v);
#define STOP 	;
#endif

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fi<<", "<<a.se<<')';
    return out;
  }
}


//Ranged Minimun Query
template <typename T>
struct RMQ{
    vector<T> dat;
    int n;
    void init(int n_){
        n = 1;
        while(n < n_) n *= 2;
 
        dat.clear();
        dat.resize(2*n-1);
        for(int i = 0; i < dat.size(); i++) dat[i] = {INF, INF};//MAX;
    }
    void update(int k, T a){
        k += n-1;
        dat[k] = a;
        while(k > 0){
            k = (k - 1) / 2;
            dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }
    T query(int a, int b, int k, int l, int r){
        if(r <= a || b <= l) return {INF, INF};//MAX;
        if(a <= l && r <= b) return dat[k];
        T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
    T query(int a, int b){
        return query(a, b, 0, 0, n);
    }
};

int main(){
	int n;
	cin >> n;
	vi p(n);
	rep(i, n) cin >> p[i];
	RMQ<pii> rmq_even, rmq_odd;
	rmq_even.init(n+10);
	rmq_odd.init(n+10);
	rep(i, n) {
		if(i&1) rmq_odd.update(i, {p[i], i});
		else rmq_even.update(i, {p[i], i});
	}
	set<pair<pii, pii> > st;
	st.insert({rmq_even.query(0, n), {0, n}});
	vi ans(n);
	rep(i, n/2) {
		auto m = *st.begin();
		pii p = m.fi, range = m.se;
		pii p2;
		if(range.fi&1) p2 = rmq_even.query(p.se, range.se);
		else p2 = rmq_odd.query(p.se, range.se);
		ans[i*2] = p.fi;
		ans[i*2+1] = p2.fi;
		//used -> max
		if(range.fi&1) {
			rmq_odd.update(p.se, {INF,INF});
			rmq_even.update(p2.se, {INF,INF});
		}
		else {
			rmq_even.update(p.se, {INF,INF});
			rmq_odd.update(p2.se, {INF,INF});
		}
		//st->div
		st.erase(m);
		if(range.fi != p.se) {
			if(range.fi&1) st.insert({rmq_odd.query(range.fi, p.se),{range.fi, p.se}});
			else st.insert({rmq_even.query(range.fi, p.se),{range.fi, p.se}});
		}
		if(range.se != p2.se+1) {
			if(p2.se&1) st.insert({rmq_even.query(p2.se+1, range.se), {p2.se+1, range.se}});
			else st.insert({rmq_odd.query(p2.se+1, range.se), {p2.se+1, range.se}});
		}
		if(p.se+1 != p2.se) {
			if(p.se&1) st.insert({rmq_even.query(p.se+1, p2.se), {p.se+1, p2.se}});
			else st.insert({rmq_odd.query(p.se+1, p2.se), {p.se+1, p2.se}});
		}
	}
	rep(i, n) {
		cout << ans[i];
		if(i == n-1) cout << endl;
		else cout << " ";
	}
}


Measured memory_bytes: 13824