#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]);
    set<int> border;
    border.insert(-1),border.insert(N);
    map<Pii,int> interval;
    interval[{-1,N}]=0;
    map<int,int> edge;
    edge[-1]=N,edge[N]=-1;
    vector<vector<int>> G(N/2+1);
    vector<Pii> ps;
    ps.push_back({-1,N});
    rep2(i,1,N/2+1){
        auto itr=border.begin();
        int l=*itr,r=*(++itr),a,b;
        while (r-l==1){
            border.erase(l);
            l=r,r=*(++border.begin());
        }
        if (abs(l)%2==1){
            a=seg0.query(l,r),seg0.update(m[a],INF);
            b=seg1.query(m[a],r),seg1.update(m[b],INF);
        }
        else{
            a=seg1.query(l,r),seg1.update(m[a],INF);
            b=seg0.query(m[a],r),seg0.update(m[b],INF);
        }
        border.insert(m[a]),border.insert(m[b]);
        interval[{a,b}]=i;
        edge[m[a]]=m[b],edge[m[b]]=m[a];
        ps.push_back({a,b});
        int le=edge[l],re=edge[r];
        if (le!=r&&abs(le-l)<abs(re-r)) swap(l,r),swap(le,re);
        if (le<l) swap(l,le);
        int par=interval[{p[l],p[le]}];
        G[par].push_back(i);
    }
    priority_queue<Pii,vector<Pii>,greater<Pii>> pq;
    pq.push(ps[0]);
    vector<int> ans;
    while (!pq.empty()){
        Pii v=pq.top(); pq.pop();
        if (v.first!=-1) ans.push_back(v.first),ans.push_back(v.second);
        for (auto nv:G[interval[v]]) pq.push(ps[nv]);
    }
    rep(i,N){
        cout << ans[i];
        if (i!=N-1) cout << ' ';
        else cout << endl;
    }
}

Measured memory_bytes: 46068