#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#ifndef ONLINE_JUDGE
#define dbg(x...) do { cout << "\033[32;1m " << #x << " -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
template<class T> using vc=vector<T>;
template<class T> using vvc=vc<vc<T>>;
template<class T> void mkuni(vector<T>&v)
{
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
}
template<class T>
void print(T x,int suc=1)
{
    cout<<x;
    if(suc==1) cout<<'\n';
    else cout<<' ';
}
template<class T>
void print(const vector<T>&v,int suc=1)
{
    for(int i=0;i<v.size();i++)
    print(v[i],i==(int)(v.size())-1?suc:2);
}
const int maxn=2e5+7;
int p[maxn];
int n;
#define lson o<<1
#define rson o<<1|1
#define Lson L,mid,lson
#define Rson mid+1,R,rson
struct sgt{
    pi mx[maxn<<2];
    pi query(int l,int r,int L=1,int R=n,int o=1)
    {
        if(l>r) return {0x3f3f3f3f,0x3f3f3f3f};
        if(l<=L&&r>=R)
            return mx[o];
        int mid=L+R>>1;
        pi ret={0x3f3f3f3f,0x3f3f3f3f};
        if(l<=mid) ret=min(ret,query(l,r,Lson));
        if(r>mid) ret=min(ret,query(l,r,Rson));
        return ret;
    }
}mx,odd,even;
void build(int L=1,int R=n,int o=1)
{
    if(L==R)
    {
        mx.mx[o].first=p[L];
        mx.mx[o].second=odd.mx[o].second=even.mx[o].second=L;
        odd.mx[o].first=even.mx[o].first=0x3f3f3f3f;
        if(L&1) odd.mx[o].first=p[L];
        else even.mx[o].first=p[L];
        return;
    }
    int mid=L+R>>1;
    build(Lson);
    build(Rson);
    mx.mx[o]=min(mx.mx[lson],mx.mx[rson]);
    odd.mx[o]=min(odd.mx[lson],odd.mx[rson]);
    even.mx[o]=min(even.mx[lson],even.mx[rson]);
}
vi G[maxn];
pi pp[maxn];
int ti=0;
int solve(int l=1,int r=n)
{
    if(l>r) return 0;
    if(l+1==r)
    {
        pp[++ti]={p[l],p[r]};
        return ti;
    }
    //assert((r-l+1)%2==0);
    pi tar;
    pi tt;
    if(l&1) 
    {
        tar=odd.query(l,r);
        tt=even.query(tar.second+1,r);
    }
    else {
        tar=even.query(l,r);
        tt=odd.query(tar.second+1,r);
    }
    //dbg(l,r,tar.first,tt.first);
    pp[++ti]={tar.first,tt.first};
    int ret=ti;
    swap(tt,tar);
    int L=solve(l,tt.second-1);
    int mid=solve(tt.second+1,tar.second-1);
    int R=solve(tar.second+1,r);
    G[ret].push_back(L);
    G[ret].push_back(mid);
    G[ret].push_back(R);
    return ret;
}
struct D{
    pi d;int id;
    bool operator<(const D&a)const{
        return d>a.d;
    }
};
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>p[i];
    build();
    int rt=solve();
    priority_queue<D> q;
    q.push(D{pp[rt],rt});
    vi ans;
    while(!q.empty())
    {
        auto u=q.top();q.pop();
        ans.push_back(u.d.first);
        ans.push_back(u.d.second);
        for(auto v:G[u.id])
        {
            if(v)
                q.push(D{pp[v],v});
        }
    }
    print(ans);
}

Measured memory_bytes: 38388