#include <bits/stdc++.h>
using namespace std;
const int MaxN = 2e5+3;
int n,a[MaxN];
set<int> chosen;
struct Segtree{
    static const int Len = 262144;
    struct Node{
        int p0,p1;
        bool inv;
    }T[(Len<<1) + 3];
    inline void pushdown(int p,int l,int r) {
        if (T[p].inv) {
            swap(T[p].p0,T[p].p1);
            if (l!=r) {
                T[p*2].inv=!T[p*2].inv;
                T[p*2+1].inv=!T[p*2+1].inv;
            }
            T[p].inv=false;
        }
    }
    inline void update(int p,int l,int r) {
        if (l!=r) {
            int mid=(l+r)/2;
            pushdown(p*2,l,mid),pushdown(p*2+1,mid+1,r);
            if (a[T[p*2].p0]<a[T[p*2+1].p0]) T[p].p0=T[p*2].p0;
            else T[p].p0=T[p*2+1].p0;
            if (a[T[p*2].p1]<a[T[p*2+1].p1]) T[p].p1=T[p*2].p1;
            else T[p].p1=T[p*2+1].p1;
        }
    }
    void invert(int p,int l,int r,int ll,int rr) {
        pushdown(p,l,r);
        if (ll<=l && r<=rr) {
            T[p].inv^=1;
            return;
        }
        int mid=(l+r)/2;
        if (ll<=mid) invert(p*2,l,mid,ll,rr);
        if (rr>mid) invert(p*2+1,mid+1,r,ll,rr);
        update(p,l,r);
    }
    void del(int p,int x,int l,int r) {
        if (l==r && l==x) {
            T[p].p0=T[p].p1=0;
            T[p].inv=false;
            return;
        }
        pushdown(p,l,r);
        int mid=(l+r)/2;
        if (x<=mid) del(p*2,x,l,mid);
        else del(p*2+1,x,mid+1,r);
        update(p,l,r);
    }
    int query0(int p,int l,int r,int ll,int rr) {
        //printf("[query0(%d,%d,%d,%d,%d):",p,l,r,ll,rr);
        pushdown(p,l,r);
        if (ll<=l && r<=rr) {
            //printf("%d]",T[p].p0);
            return T[p].p0;
        }
        int ret=0,mid=(l+r)/2;
        if (ll<=mid) {
            int p0=query0(p*2,l,mid,ll,rr);
            if (a[p0]<a[ret]) ret=p0;
        }
        if (rr>mid) {
            int p0=query0(p*2+1,mid+1,r,ll,rr);
            if (a[p0]<a[ret]) ret=p0;
        }
        //printf("%d]",ret);
        return ret;
    }
    int query1(int p,int l,int r,int ll,int rr) {
        //printf("[query1(%d,%d,%d,%d,%d):",p,l,r,ll,rr);
        pushdown(p,l,r);
        if (ll<=l && r<=rr) {
            //printf("%d]",T[p].p1);
            return T[p].p1;
        }
        int ret=0,mid=(l+r)/2;
        if (ll<=mid) {
            int p0=query1(p*2,l,mid,ll,rr);
            if (a[p0]<a[ret]) ret=p0;
        }
        if (rr>mid) {
            int p0=query1(p*2+1,mid+1,r,ll,rr);
            if (a[p0]<a[ret]) ret=p0;
        }
        //printf("%d]",ret);
        return ret;
    }
    void build(int p,int l,int r) {
        if (l==r) {
            T[p].p0=T[p].p1=0;
            if (l%2) T[p].p1=l;
            else T[p].p0=l;
            T[p].inv=false;
            return;
        }
        int mid=(l+r)/2;
        build(p*2,l,mid);build(p*2+1,mid+1,r);
        update(p,l,r);
    }
}seg;
int ans[MaxN];
int main() {
    scanf("%d",&n);
    a[0]=0x7fffffff;
    for (int i=1;i<=n;++i) scanf("%d",a+i);
    seg.build(1,1,n);
    chosen.insert(0);chosen.insert(n+1);
    for (int i=1;i<=n/2;++i) {
        int p1=seg.query1(1,1,n,1,n);
        int ed = *(chosen.lower_bound(p1))-1;
        int p2=seg.query0(1,1,n,p1+1,ed);
        ans[i*2-1]=a[p1],ans[i*2]=a[p2];
        seg.del(1,p1,1,n),seg.del(1,p2,1,n);
        seg.invert(1,1,n,p1+1,p2-1);
        chosen.insert(p1),chosen.insert(p2);
    }
    for (int i=1;i<=n;++i) printf("%d ",ans[i]);
    return 0;
}

Measured memory_bytes: 18560