//marico el que lo lea
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <stdlib.h>
#include <assert.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> ii;

void fastIO() {
	std::ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
}

#define FOR(i,f,t) for(int i=f; i<(int)t; i++)
#define FORR(i,f,t) for(int i=f; i>(int)t; i--)
#define FORE(i,c) for(auto i = (c).begin(); i != (c).end(); i++)
#define pb push_back
#define all(obj) obj.begin(), obj.end()
#define ms(obj, val) memset(obj, val, sizeof(obj))
#define ms2(obj, val, sz) memset(obj, val, sizeof(obj[0])*sz)

#define fst first
#define snd second

template<typename T, typename U> inline void mnze(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void mxze(T &x, U y) { if(x < y) x = y; }

void _scan( int &x ) { scanf("%d",&x); }
void _scan( long long &x ) { scanf("%lld",&x); }
void _scan( double &x ) { scanf("%lf",&x); }
void _scan( char &x ) { scanf(" %c",&x); }
void _scan( char *x ) { scanf("%s",x); }
void scan() {}
template<typename T, typename... U>
void scan( T& head, U&... tail ) { _scan(head); scan(tail...);}

template<typename T> void _dbg(const char* sdbg, T h) { cerr<<sdbg<<"="<<h<<"\n"; }
template<typename T, typename... U> void _dbg(const char* sdbg, T h, U... t) {
	while(*sdbg != ',')cerr<<*sdbg++; cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define debugv(x) {{cerr <<#x <<" = "; FORE(_i, (x)) cerr <<*_i <<", "; cerr <<"\n"; }}
#define debuga(x, sz) {{cerr <<#x <<" = "; FOR(_i, 0, sz) cerr << x[_i] <<", "; cerr <<"\n"; }}
#else
#define debug(...) (__VA_ARGS__)
#define debugv(x)
#define debuga(x, sz)
#define cerr if(0)cout
#endif

///////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////

struct stnode{
    ii even, odd;
    int len;
	void merge(stnode& L, stnode& R){
        if(L.len % 2 == 0){
            even = min(L.even, R.even);
            odd = min(L.odd, R.odd);
        }else{
            even = min(L.even, R.odd);
            odd = min(L.odd, R.even);
        }
        len = L.len+R.len;
    }
	void operator=(ii x){
        len = 1;
        odd = {2e6+6,-1};
        even = x;
    }
};
struct ST{
	vector<stnode> T;
    vi a;
	int N;
	void init(int n, vi &A){
		T.resize(4*n + 4);
		N = n;
        a = A;
	}
	void build(){build(1,0,N);}
	void build(int id, int l, int r){
		if(r - l < 2){
			T[id] = {a[l],l};
			return;
		}
		int M = (l+r)>>1, L=id<<1, R=L|1;
		build(L, l, M); build(R, M, r);
		T[id].merge(T[L],T[R]);
	}

	stnode query(int x, int y){return query(x,y,1,0,N);}
	stnode query(int x, int y, int id, int l, int r){
		if(x == l && y == r)	return T[id];
		int M = (l+r)>>1, L=id<<1, R=L|1;
		if(x>=M)	return query(x,y,R,M,r);
		if(y<=M)	return query(x,y,L,l,M);
		stnode res,ln=query(x, M, L, l, M),rn=query(M, y, R, M, r);
		return res.merge(ln, rn), res;
	}

};

ST st;
struct seg{
    int l, r, bst;
    seg(int _l, int _r){
        l=_l;
        r=_r;
        bst = st.query(l, r+1).even.fst;
    }
    bool operator<(const seg &o) const{
        return bst > o.bst;
    }
};

const int MAXN = 2e5+5;

int N;
vi p;

int main(){
    scan(N);
    p.resize(N);
    FOR(i,0,N) scan(p[i]);
    st.init(N, p);
    st.build();
    priority_queue<seg> pq;
    pq.push(seg(0,N-1));
    while(!pq.empty()){
        seg s = pq.top(); pq.pop();
        int i = st.query(s.l, s.r+1).even.snd;
        printf("%d ", p[i]);
        int j = st.query(i, s.r+1).odd.snd;
        printf("%d ",p[j]);
        if(s.l < i) pq.push(seg(s.l, i-1));
        if(j < s.r) pq.push(seg(j+1, s.r));
        if(i+1 < j) pq.push(seg(i+1, j-1));
    }
    printf("\n");
}


Measured memory_bytes: 19320