#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <functional>

#define mp make_pair
#define pb push_back
#define mes(a,b) memset(a,b,sizeof(a))
#define mes0(a) memset(a,0,sizeof(a))
#define lson l,mid,pos<<1
#define rson mid+1,r,pos<<1|1
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define fi first
#define se second
#define sss(a) a::iterator
#define all(a) a.begin(),a.end()

using namespace std;

typedef double DB;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<long long ,int> pli;
typedef pair<int,long long > pil;
typedef pair<string,int> psi;
typedef pair<long long ,long long > pll;

const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const int maxn = 200000+10;
int s[maxn];
int n;
pii tree1[maxn<<2],tree2[maxn<<2];
vector<pii> ans;
vector <int> nt[123456];
pii query(pii tree[],int l,int r,int pos,int l1,int r1)
{
    if (l>=l1&&r<=r1){
        return tree[pos];
    }
    int mid=(l+r)>>1;
    pii ret=mp(inf,inf);
    if (mid>=l1)ret=query(tree,lson,l1,r1);
    if (mid+1<=r1)ret=min(ret,query(tree,rson,l1,r1));
    return ret;
}
void push_up(pii tree[],int pos)
{
    tree[pos]=min(tree[pos<<1],tree[pos<<1|1]);
}
void upd(pii tree[],int l,int r,int pos,int x,int v)
{
    if (l==r){
        tree[pos].fi=v;
        tree[pos].se=x;
        return ;
    }
    int mid=(l+r)>>1;
    if (mid>=x)upd(tree,lson,x,v);
    else upd(tree,rson,x,v);
    push_up(tree,pos);
}
void getmin(int l,int r,vector <int> & nn)
{
    if (l&1){
        pii st=query(tree2,1,n,1,l,r);
        pii now=query(tree1,1,n,1,st.se,r);
        ans.pb(mp(st.fi,now.fi));
        nn.pb(ans.size()-1);
        int tt=ans.size()-1;
        upd(tree2,1,n,1,st.se,inf);
        upd(tree1,1,n,1,now.se,inf);
        if (st.se-l>=3)
        getmin(l,st.se,nt[tt]);
        if (now.se-st.se>=3)
        getmin(st.se,now.se,nt[tt]);
        if (r-now.se>=3)
        getmin(now.se,r,nt[tt]);
    }else{
        pii st=query(tree1,1,n,1,l,r);
        pii now=query(tree2,1,n,1,st.se,r);
        ans.pb(mp(st.fi,now.fi));
        nn.pb(ans.size()-1);
        int tt=ans.size()-1;
        upd(tree1,1,n,1,st.se,inf);
        upd(tree2,1,n,1,now.se,inf);
        if (st.se-l>=3)
        getmin(l,st.se,nt[tt]);
        if (now.se-st.se>=3)
        getmin(st.se,now.se,nt[tt]);
        if (r-now.se>=3)
        getmin(now.se,r,nt[tt]);
    }
}
void bfs()
{
    int flag=0;
    set<pair<pii,int> > put;
    put.insert(mp(ans[nt[0][0]],1));
    while (!put.empty()){
        if (flag)printf(" ");
        flag=1;
        printf("%d %d",put.begin()->fi.fi,put.begin()->fi.se);
        pair<pii,int> tmp=*put.begin();
        put.erase(put.begin());
        int pos=tmp.se;
        for (int i=0;i<nt[pos].size();i++){
            put.insert(mp(ans[nt[pos][i]],nt[pos][i]));
        }
    }
}
int main()
{
    memset(tree1,0x3f,sizeof(tree1));
    memset(tree2,0x3f,sizeof(tree2));
    int x;
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d",&x);
        if (i&1)upd(tree1,1,n,1,i,x);
        else upd(tree2,1,n,1,i,x);
    }
    int flag=0;
    ans.pb(mp(0,0));
    getmin(0,n+1,nt[0]);
    bfs();
    return 0;
}


Measured memory_bytes: 28660