#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using namespace std;
using uint = unsigned int;
using ll = long long;
const int M = 1e9 + 7;
const ll MLL = 1e18L + 9;
#pragma unused(M)
#pragma unused(MLL)
#ifdef LOCAL
#include"rprint.hpp"
#else
template <ostream& out = cout, class... T> void prints(T&&...){ }
template <ostream& out = cout, class... T> void printd(T&&...){ }
template <ostream& out = cout, class... T> void printde(T&&...){ }
template <ostream& out = cout, class... T> void printb(T&&...){ }
template <ostream& out = cout, class... T> void printArr(T&&...){ }
#endif

struct SegTree{
    SegTree *l, *r;
    int left, right;
    pair<ll, int> value = {M, M};
    SegTree(int size):SegTree(0, size - 1){ }
    SegTree(int st, int lt): left(st), right(lt){
        prints('c', st, lt);
        if(left == right){
            l = r = nullptr;
        }else{
            // l = new SegTree(left, (right - left) / 2 + left);
            // r = new SegTree((right - left) / 2 + left + 1, right);
            l = new SegTree(left, (right + left) / 2);
            r = new SegTree((right + left) / 2 + 1, right);
        }
    }
    void set(int idx, pair<ll, int> val){
        if(right < idx || idx < left){ return; }
        value = min(value, val);
        prints(left, right, value);
        if(left != idx || right != idx){
            l -> set(idx, val);
            r -> set(idx, val);
        }
    }
	pair<ll, int> getmin(int le, int re){
		if(right < le || re < left){ return {M, M}; }
		if(le <= left && right <= re){
			return value;
		}
		return min(l -> getmin(le, re), r -> getmin(le, re));
	}
};

vector<pair<int, int>> solve(vector<int>& ps, SegTree& ste, SegTree& sto, int beg, int end, bool rev = false){
    pair<int, int> mini = {M, M};
    // for(int i = beg; i < end; i += 2){
    //     mini = min(mini, {ps[i], i});
    // }
    prints(beg, end);
    auto p1 = (rev ? sto : ste).getmin(beg, end - 1);
    pair<int, int> mini2 = {M, M};
    // for(int i = mini.second + 1; i < end; i += 2){
    //     mini2 = min(mini2, {ps[i], i});
    // }
    auto p2 = (rev ? ste : sto).getmin(p1.second, end - 1);
    vector<pair<int, int>> r1, r2, r3, ret = {{p1.first, p2.first}};//, ret;
    int i1 = 0, i2 = 0, i3 = 0, i0 = 0;
    if(beg < p1.second){
        r1 = solve(ps, ste, sto, beg, p1.second, rev);
    }
    if(p1.second + 1 < p2.second){
        r2 = solve(ps, ste, sto, p1.second + 1, p2.second, !rev);
    }
    if(p2.second + 1 < end){
        r3 = solve(ps, ste, sto, p2.second + 1, end, rev);
    }
    r1.push_back({M, M});
    r2.push_back({M, M});
    r3.push_back({M, M});
    // r0.push_back({M, M});
    bool cont = true;
    while(cont){
        cont = false;
        if(i1 < r1.size() - 1 && r1[i1] < r2[i2] && r1[i1] < r3[i3]/* && r1[i1] < r0[i0]*/){ cont = true; ret.push_back(r1[i1++]); }
        if(i2 < r2.size() - 1 && r2[i2] < r1[i1] && r2[i2] < r3[i3]/* && r2[i2] < r0[i0]*/){ cont = true; ret.push_back(r2[i2++]); }
        if(i3 < r3.size() - 1 && r3[i3] < r1[i1] && r3[i3] < r2[i2]/* && r3[i3] < r0[i0]*/){ cont = true; ret.push_back(r3[i3++]); }
        // if(i0 < r0.size() - 1 && r0[i0] < r1[i1] && r0[i0] < r2[i2] && r0[i0] < r3[i3]){ cont = true; ret.push_back(r0[i0++]); }
    }
    printd(ret);
    return ret;
}

int main(){
    int n; cin >> n;
    vector<int> ps(n);
    // SegTree ste((n + 1)/ 2), sto(n / 2);
    SegTree ste(n), sto(n);
    for(int i = 0; i < n; i++){
        cin >> ps[i];
        (i & 1 ? sto : ste).set(i, {ps[i], i});
    }
    // auto ans = solve(ps, ste, sto, 0, n);
    // for(int i = 0; i < n / 2; i++){
    //     cout << ans[i].first << ' ' << ans[i].second << ' ';
    // }
    struct Elem {
        int b, l, v, idx;
        bool rev(){ return b & 1; }
        bool operator < (const Elem& elem) const{
            return v > elem.v;
        }
    };
    auto make = [&](int beg, int lst){
        pair<ll, int> ret;
        if(beg & 1){
            ret = sto.getmin(beg, lst);
        }else{
            ret = ste.getmin(beg, lst);
        }
        prints(beg, lst, (int)ret.first, ret.second);
        return Elem{beg, lst, (int)ret.first, ret.second};
    };
    priority_queue<Elem> pq;
    auto push = [&](int beg, int lst){
        if(beg < lst && lst <= n){
            pq.push(make(beg, lst));
        }
    };
    pq.push(make(0, n - 1));
    vector<int> ans;
    while(pq.size()){
        auto e = pq.top(); pq.pop();
        ans.push_back(e.v);
        auto p = (e.idx & 1 ? ste : sto).getmin(e.idx + 1, e.l);
        ans.push_back(p.first);
        push(e.b, e.idx - 1);
        push(e.idx + 1, p.second - 1);
        push(p.second + 1, e.l);
    }
    for(int i = 0; i < n; i++){
        cout << ans[i] << ' ';
    }
    return 0;
}


Measured memory_bytes: 41336