#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_map>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>
#include<bitset>
#include<list>

using namespace std;

#define ll long long int

ll const MOD = 1000000007;
ll const INF = (long long int)1 << 61;

ll mypow(ll x,ll n){
    ll ret = 1;
    while(n > 0){
        if(n&1){
            ret = (ret*x)%MOD;
        }
        x = (x*x)%MOD;
        n >>= 1;
    }
    return ret;
}

template<typename dataType>
class SegmentTree{
    int dataSize;
    dataType initialVal;
    std::vector<dataType> tree;
    std::function<dataType(dataType,dataType)> addFunc;
    std::function<dataType(dataType,dataType)> extFunc;

    void internalUpdate(int pointedIndex){
        while(pointedIndex > 1){
            pointedIndex >>= 1;
            tree[pointedIndex] = extFunc(tree[pointedIndex*2],tree[pointedIndex*2+1]);
        }
    }

public:

    SegmentTree(int N, dataType init,
                function<dataType(dataType,dataType)> f1 = [](dataType a,dataType b)->dataType{return a+b;},
                function<dataType(dataType,dataType)> f2 = [](dataType a,dataType b)->dataType{return a+b;})
                :initialVal(init),addFunc(f1),extFunc(f2){
                    dataSize = 1;
                    while(dataSize < N){
                        dataSize *= 2;
                    }
                    tree = std::vector<dataType>(dataSize*2,initialVal);
                }

    bool updateQuery(int index,dataType newVal){
        if(index < 1 || index > dataSize){
            return false;
        }
        int pointedIndex = dataSize + index - 1;
        tree[pointedIndex] = newVal;
        internalUpdate(pointedIndex);
        return true;
    }

    bool addQuery(int index,dataType newVal){
        if(index < 1 || index > dataSize){
            return false;
        }
        int pointedIndex = dataSize + index - 1;
        tree[pointedIndex] = addFunc(tree[pointedIndex],newVal);
        internalUpdate(pointedIndex);
        return true;
    }

    dataType getQuery(int leftIndex , int rightIndex){
        if(leftIndex > rightIndex || leftIndex < 1 || rightIndex > dataSize){
            return initialVal;
        }else if(leftIndex == rightIndex){
            return tree[dataSize + leftIndex - 1];
        }

        int leftPointedIndex = dataSize + leftIndex - 1;
        int rightPointedIndex = dataSize + rightIndex - 1;

        dataType leftVal = tree[leftPointedIndex];
        dataType rightVal = tree[rightPointedIndex];
        
        while(true){
            bool wasLeftEven = (leftPointedIndex % 2 == 0);
            bool wasRightEven = (rightPointedIndex % 2 == 0);

            leftPointedIndex >>= 1;
            rightPointedIndex >>= 1;

            if(leftPointedIndex == rightPointedIndex){
                return extFunc(leftVal,rightVal);
            }

            if(wasLeftEven){
                leftVal = extFunc(leftVal,tree[leftPointedIndex*2 + 1]);
            }

            if(!wasRightEven){
                rightVal = extFunc(rightVal,tree[rightPointedIndex*2]);
            }
        }

        return initialVal;
    }
};

int rec(int l,int r,vector<list<int>> &edge,vector<tuple<int,int,int>> &vertex,const vector<int> &v,SegmentTree<pair<int,int>> &ost,SegmentTree<pair<int,int>> &est){
    if(r - l == 1){
        vertex.push_back(make_tuple(v[l],v[r],vertex.size()));
        return vertex.size()-1;
    }

    pair<int,int> ml,mr;

    if(l%2 == 1){
        ml = ost.getQuery(l,r);
        mr = est.getQuery(ml.second+1,r);
    }else{
        ml = est.getQuery(l,r);
        mr = ost.getQuery(ml.second+1,r);
    }

    int myid = vertex.size();

    vertex.push_back(make_tuple(ml.first,mr.first,myid));

    if(ml.second != l){
        edge[myid].push_back(rec(l,ml.second-1,edge,vertex,v,ost,est));
    }
    if(mr.second - ml.second != 1){
        edge[myid].push_back(rec(ml.second+1,mr.second-1,edge,vertex,v,ost,est));
    }
    if(mr.second != r){
        edge[myid].push_back(rec(mr.second+1,r,edge,vertex,v,ost,est));
    }

    return myid;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<int> a(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    function<pair<int,int>(pair<int,int>,pair<int,int>)> func1,func2;
    pair<int,int> init = {1 << 29,0};

    func1 = [](pair<int,int> a,pair<int,int> b)->pair<int,int>{
        return {a.first + b.first,a.second};
    };

    func2 = [](pair<int,int> a,pair<int,int> b)->pair<int,int>{
        if(a.first > b.first){
            return b;
        }else{
            return a;
        }
    };

    SegmentTree<pair<int,int>> oddst(n,init,func1,func2);
    SegmentTree<pair<int,int>> evenst(n,init,func1,func2);

    for(int i = 1; i <= n; i++){
        if(i%2 == 0){
            evenst.updateQuery(i,{a[i],i});
        }else{
            oddst.updateQuery(i,{a[i],i});
        }
    }

    vector<list<int>> edge(n);
    vector<tuple<int,int,int>> vertex;

    rec(1,n,edge,vertex,a,oddst,evenst);

    priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>> pq;

    vector<int> ans;

    pq.push(vertex[0]);

    vector<bool> used(vertex.size(),false);

    while(!pq.empty()){
        auto t = pq.top();
        if(used[get<2>(t)]){
            continue;
        }
        pq.pop();
        used[get<2>(t)] = true;
        ans.push_back(get<0>(t));
        ans.push_back(get<1>(t));

        for(auto itr = edge[get<2>(t)].begin(); itr != edge[get<2>(t)].end(); itr++){
            pq.push(vertex[*itr]);
        }
    }

    for(int i = 0; i < n; i++){
        if(i > 0)cout << " ";
        cout << ans[i];
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 76020