#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 200005;

int n,a[maxn];
vector<pair<int,int>> pr;
vector<int>e[maxn];
struct ST {
    int l,r,val[2],idx[2];
} st[maxn*4];
void build(int id,int l,int r) {
    st[id].l=l,st[id].r=r;
    st[id].val[0]=st[id].val[1]=st[id].idx[0]=st[id].idx[1]=n+1;
    if(l==r) {
        st[id].val[l&1]=a[l];
        st[id].idx[l&1]=l;
        return;
    }
    int m=(l+r)>>1;
    build(id<<1,l,m);
    build(id<<1|1,m+1,r);
    for(int i=0; i<2; i++) {
        if(st[id<<1].val[i]<st[id<<1|1].val[i]) {
            st[id].val[i]=st[id<<1].val[i];
            st[id].idx[i]=st[id<<1].idx[i];
        } else {
            st[id].val[i]=st[id<<1|1].val[i];
            st[id].idx[i]=st[id<<1|1].idx[i];
        }
    }
}
int query(int id, int l,int r,int flag) {
    if(st[id].l==l&&st[id].r==r) {
        return st[id].idx[flag];
    }
    int m=(st[id].l+st[id].r)>>1;
    if(r<=m)return query(id<<1,l,r,flag);
    if(l>m)return query(id<<1|1,l,r,flag);
    int lret=query(id<<1,l,m,flag);
    int rret=query(id<<1|1,m+1,r,flag);
    if(a[lret]>a[rret])return rret;
    return lret;
}

void dfs(int l,int r,int fa_idx) {
    if(l>r)return;
    if(l+1==r) {
        int sz=pr.size();
        pr.push_back(make_pair(l,r));
        e[fa_idx].push_back(sz);
        return;
    }
    int idxl=query(1,l,r,l&1);
    int idxr=query(1,idxl+1,r,(l+1)&1);
    int sz=pr.size();
    pr.push_back(make_pair(idxl,idxr));
    e[fa_idx].push_back(sz);
    dfs(l,idxl-1,sz);
    dfs(idxl+1,idxr-1,sz);
    dfs(idxr+1,r,sz);
}

struct cmp {
    bool operator()(int x,int y) {
        auto prx=make_pair(a[pr[x].first],a[pr[x].second]);
        auto pry=make_pair(a[pr[y].first],a[pr[y].second]);
        return prx>pry;
    }
};

struct Item {
  int l,r,fa_idx;
  Item(int l,int r,int fa_idx):l(l),r(r),fa_idx(fa_idx){}
};

int main() {
    //freopen("in.cpp","r",stdin);
    cin>>n;
    for(int i=1; i<=n; i++)cin>>a[i];
    a[n+1]=n+1;
    build(1,1,n);
    int l=1,r=n;
    int idxl=query(1,l,r,l&1);
    int idxr=query(1,idxl+1,r,(l+1)&1);
    int sz=pr.size();
    pr.push_back(make_pair(idxl,idxr));
    queue<Item>myque;
    myque.push(Item(l,idxl-1,sz));
    myque.push(Item(idxl+1,idxr-1,sz));
    myque.push(Item(idxr+1,r,sz));
    while(!myque.empty()){
      auto x=myque.front();
      myque.pop();
      int l=x.l,r=x.r,fa_idx=x.fa_idx;
      if(l>r)continue;
    if(l+1==r) {
        int sz=pr.size();
        pr.push_back(make_pair(l,r));
        e[fa_idx].push_back(sz);
        continue;
    }
    int idxl=query(1,l,r,l&1);
    int idxr=query(1,idxl+1,r,(l+1)&1);
    int sz=pr.size();
    pr.push_back(make_pair(idxl,idxr));
    e[fa_idx].push_back(sz);
    myque.push(Item(l,idxl-1,sz));
    myque.push(Item(idxl+1,idxr-1,sz));
    myque.push(Item(idxr+1,r,sz));
    }
    priority_queue<int,vector<int>,cmp>que;
    que.push(0);
    vector<int>ans;
    while(!que.empty()) {
        int x=que.top();
        que.pop();
        ans.push_back(a[pr[x].first]);
        ans.push_back(a[pr[x].second]);
        for(int i=0; i<e[x].size(); i++) {
            que.push(e[x][i]);
        }
    }
    for(int i=0; i<n; i++)printf("%d%c",ans[i],i==n-1?'\n':' ');
    return 0;
}


Measured memory_bytes: 26484