#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<(n);++i)
#define rep2(i,a,b) for (ll i=(a);i<(b);++i)
#define debug(x) cout << #x << '=' << x << endl
#define all(v) (v).begin(),(v).end()
const ll MOD=1e9+7;
//const ll MOD=998244353;
const ll INF=1e9;
const ll IINF=1e18;
const double EPS=1e-8;
const double pi=acos(-1);

template<class T> inline bool chmin(T &a,T b){
    if (a>b){a=b; return true;}
    return false;
}
template<class T> inline bool chmax(T &a,T b){
    if (a<b){a=b; return true;}
    return false;
}

template<typename Monoid>
struct SegmentTree{
    private:
    typedef function<Monoid(Monoid,Monoid)> F;
    typedef function<Monoid(Monoid,Monoid)> G;
    int n;
    F f;
    G g;
    Monoid id;
    vector<Monoid> dat;
    public:
    SegmentTree(int n_,F f,G g,Monoid id):f(f),g(g),id(id){init(n_);};
    void init(int n_){
        n=1;
        while (n<n_) n*=2;
        dat.resize(2*n-1,id);
    }
    void build(vector<Monoid> v){
        int n_=v.size();
        rep(i,n_) dat[i+n-1]=v[i];
        for (int i=n-2;i>=0;i--) dat[i]=f(dat[2*i+1],dat[2*i+2]);
    }
    void update(int i,Monoid a){
        i+=n-1;
        dat[i]=g(dat[i],a);
        while (i>0){
            i=(i-1)/2;
            dat[i]=f(dat[2*i+1],dat[2*i+2]);
        }
    }
    Monoid query(int a,int b,int k,int l,int r){
        if (r<=a||b<=l) return id;
        if (a<=l&&r<=b) return dat[k];
        Monoid vl=query(a,b,2*k+1,l,(l+r)/2);
        Monoid vr=query(a,b,2*k+2,(l+r)/2,r);
        return f(vl,vr);
    }
    Monoid query(int a,int b){
        return query(a,b,0,0,n);
    }
    Monoid operator[](int i){
        return dat[i+n-1];
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<int> P(N);
    rep(i,N) cin >> P[i];
    map<int,int> m;
    rep(i,N) m[P[i]]=i;
    auto f=[](int a,int b){return min(a,b);};
    auto g=[](int a,int b){return b;};
    SegmentTree<int> seg0(N,f,g,INF),seg1(N,f,g,INF);
    for (int i=0;i<N;i+=2) seg0.update(i,P[i]);
    for (int i=1;i<N;i+=2) seg1.update(i,P[i]);
    vector<int> ans;
    priority_queue<Pii,vector<Pii>,greater<Pii>> pq;
    set<int> border;
    border.insert(-1),border.insert(N);
    int fa=seg0.query(-1,N),fb=seg1.query(m[fa],N);
    seg0.update(m[fa],INF),seg1.update(m[fb],INF);
    pq.push({fa,fb});
    while (!pq.empty()){
        Pii p=pq.top(); pq.pop();
        ans.push_back(p.first),ans.push_back(p.second);
        auto itr=border.upper_bound(m[p.first]);
        int r=*itr,l=*(--itr);
        int cl=m[p.first],cr=m[p.second];
        vector<Pii> v={{l,cl},{cl,cr},{cr,r}};
        rep(i,3){
            Pii q=v[i];
            int ql=q.first,qr=q.second,a,b;
            if (qr-ql==1) continue;
            if (abs(ql)%2==1){
                a=seg0.query(ql,qr),seg0.update(m[a],INF);
                b=seg1.query(m[a],qr),seg1.update(m[b],INF);
            }
            else {
                a=seg1.query(ql,qr),seg1.update(m[a],INF);
                b=seg0.query(m[a],qr),seg0.update(m[b],INF);
            }
            pq.push({a,b});
        }
        border.insert(cl),border.insert(cr);
    }
    rep(i,N){
        cout << ans[i];
        if (i!=N-1) cout << ' ';
        else cout << endl;
    }
}

Measured memory_bytes: 26224