#include<cstdio>
const int inf = 1e7+7;
int a[200005];
int bit[200005];
int answer[200005];
struct SegmentT{
    int l,r;
    int minn[2],pos[2];
    int offer, offerP;
    int tag;
    int c;
    SegmentT(){
        minn[0] = minn[1] = inf;
        pos[0] = pos[1] = 0;
        offer = inf;
        offerP = -1;
        c = tag = 0;
    }
};
SegmentT t[800005];
//point change, segment flip, segment ask...

SegmentT merge(SegmentT& u,SegmentT& v){
    SegmentT res;
    res.l = u.l, res.r = v.r;
    for(int i = 0; i < 2; i++){
        if(u.minn[i]<v.minn[i]){
            res.minn[i] = u.minn[i];
            res.pos[i] = u.pos[i];
        }
        else{
            res.minn[i] = v.minn[i];
            res.pos[i] = v.pos[i];
        }
    }
    if(u.tag==v.tag) res.tag = u.tag;
    else res.tag = -1;
    if(u.offer<v.offer){
        res.offer = u.offer;
        res.offerP = u.offerP;
    }
    else{
        res.offer = v.offer;
        res.offerP = v.offerP;
    }
    return res;
}

void singleSpread(SegmentT& u){
    if(u.tag==1){
        u.tag = 0;
        u.offer = u.minn[0]; u.offerP = u.pos[0];
    }
    else{
        u.tag = 1;
        u.offer = u.minn[1]; u.offerP = u.pos[1];
    }
    u.c = !u.c;
}

void spread(int p){
    if(t[p].c!=0){
        t[p].c = 0;
        singleSpread(t[2*p]);
        singleSpread(t[2*p+1]);
    }
}

void build(int p,int l,int r){
    t[p].l = l, t[p].r = r, t[p].tag = 1, t[p].c = 0;
    if(l==r){
        int u = l%2; int v = !u;
        t[p].minn[u] = a[l], t[p].pos[u] = l;
        t[p].minn[v] = inf, t[p].pos[v] = -1;
        t[p].offer = t[p].minn[t[p].tag];
        t[p].offerP = t[p].pos[t[p].tag];
    }
    else{
        int m = (l+r)/2;
        build(2*p,l,m);
        build(2*p+1,m+1,r);
        t[p] = merge(t[2*p],t[2*p+1]);
    }
}

void segmentFlip(int p,int l,int r){
    if(l<=t[p].l && r>=t[p].r){
        singleSpread(t[p]);
    }
    else{
        spread(p);
        int m = (t[p].l+t[p].r)/2;
        if(l<=m) segmentFlip(2*p,l,r);
        if(r>=m+1) segmentFlip(2*p+1,l,r);
        t[p] = merge(t[2*p],t[2*p+1]);
    }
}

void pointChange(int p,int x){
    if(t[p].l==t[p].r){
        for(int i = 0; i < 2; i++) t[p].minn[i] = inf, t[p].pos[i] = -1;
        t[p].offer = inf, t[p].offerP = -1;
    }
    else{
        spread(p);
        int m = (t[p].l+t[p].r)/2;
        if(x<=m) pointChange(2*p,x);
        else pointChange(2*p+1,x);
        t[p] = merge(t[2*p],t[2*p+1]);
    }
}

SegmentT segAsk(int p,int l,int r){
    if(l<=t[p].l && r>=t[p].r) return t[p];
    else{
        spread(p);
        int m = (t[p].l+t[p].r)/2;
        SegmentT u,v;
        if(l<=m) u = segAsk(2*p,l,r);
        if(r>=m+1) v = segAsk(2*p+1,l,r);
        return merge(u,v);
    }
}

void change(int p,int v,int n){
    while(p<=n){
        bit[p] += v;
        p += p&-p;
    }
}

int ask(int p){
    int res = 0;
    while(p!=0){
        res += bit[p];
        p -= p&-p;
    }
    return res;
}

int getBorder(int p,int upper){
    int L = p, R = upper;
    int res = -1;
    int base = ask(p);
    while(L<=R){
        int M = (L+R)/2;
        if(ask(M)==base){
            res = M;
            L = M+1; 
        }
        else R = M-1;
    }
    return res;
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
    build(1,1,n);
    for(int i = 1; i <= n/2; i++){
        SegmentT res = t[1];
        int v0 = res.offer, p0 = res.offerP;
        //printf("v0 = %d, p0 = %d\n",v0,p0);
        answer[2*i-1] = v0;
        int upper = getBorder(p0,n);
        res = segAsk(1,p0+1,upper);
        int tag = !(p0%2);
        int v1 = res.minn[tag], p1 = res.pos[tag];
        //printf("v1 = %d, p1 = %d\n",v1,p1);
        answer[2*i] = v1; 
        pointChange(1,p0); 
        pointChange(1,p1);
        if(p1!=p0+1) segmentFlip(1,p0+1,p1-1);
        change(p0,1,n);
        change(p1,1,n);
    }
    for(int i = 1; i <= n; i++) printf("%d ",answer[i]);
    printf("\n");
    return 0;
}


Measured memory_bytes: 35328