#include <bits/stdc++.h>
using namespace std;

// macros
#define overload_rep(_1, _2 ,_3 ,name, ...) name
#define re_p(i, n) for(int i = 0; i < (n); ++i)
#define r_ep(i, x, y) for(int i = (x); i <= (y); ++i)
#define rep(...) overload_rep(__VA_ARGS__, r_ep, re_p,)(__VA_ARGS__)
#define all(a) a.begin(), a.end()
#ifndef STOP_DEBUG
#define debug(...)\
    do { cerr << boolalpha << "[" << #__VA_ARGS__ << "]:";\
    debug_cerr(__VA_ARGS__); cerr << noboolalpha; } while (0)
#else
#define debug(...)
#endif

// functions
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
void debug_cerr(){ cerr << '\n'; }
template<class Head, class... Tail>
void debug_cerr(Head head, Tail... tail){
    cerr << ' ' << head;
    debug_cerr(tail...);
}

// cin/cout setup
struct IoSetup{
    IoSetup(){
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} iosetup;

// Let's get AC!

template<class T> 
struct SparseTable{ // Sparse Table
private:
    vector<vector<T>> dat;
    vector<int> height;
public:
    SparseTable(){}
    SparseTable(const vector<T> &vec){ init(vec); }
    void init(const vector<T> &vec){
        int n = (int)vec.size(), h = 0;
        while((1 << h) <= n)h++;
        dat.assign(h, vector<T>(1 << h));
        height.assign(n + 1, 0);
        for(int i = 2; i <= n; i++)height[i] = height[i >> 1] + 1;
        for(int i = 0; i < n; ++i)dat[0][i] = vec[i];
        for(int i = 1; i < h; ++i){
            for(int j = 0; j < n; ++j){
                dat[i][j] = min<T>(dat[i - 1][j], dat[i - 1][min(j + (1 << (i - 1)), n - 1)]);
            }
        }
    }
    inline T get(int a, int b){
        int t = height[b - a];
        return min<T>(dat[t][a], dat[t][b - (1 << t)]); 
    }
};

struct vpos{
    int val, pos;
    vpos(int v = 0, int p = 0) : val(v), pos(p) {}
    bool operator < (vpos vp) const { return val < vp.val; }
    bool operator > (vpos vp) const { return val > vp.val; }
};

struct sec{
    int l, r;
    vpos vp;
    sec(int l, int r, vpos vp) : l(l), r(r), vp(vp) {}
    bool operator < (sec sc) const { return vp < sc.vp; }
    bool operator > (sec sc) const { return vp > sc.vp; }
};

const int inf = 300000;

int main(){

    int N;
    cin >> N;
    vector<vpos> vodd(N), veven(N);
    rep(i, N){
        int p;
        cin >> p;
        if(i & 1)veven[i] = vpos(p, i), vodd[i] = vpos(inf, i);
        else vodd[i] = vpos(p, i), veven[i] = vpos(inf, i);
    }

    SparseTable<vpos> odd(vodd), even(veven);
    priority_queue<sec, vector<sec>, greater<sec>> que;
    que.push(sec(0, N, odd.get(0, N)));

    vector<int> ans;
    while(!que.empty()){
        sec now = que.top(); que.pop();
        int l = now.l, r = now.r, nl = now.vp.pos, nr;
        ans.push_back(now.vp.val);
        if(l & 1){
            vpos tmp = odd.get(nl, r);
            ans.push_back(tmp.val);
            nr = tmp.pos;
            if(l < nl)que.push(sec(l, nl, even.get(l, nl)));
            if(nl + 1 < nr)que.push(sec(nl + 1, nr, odd.get(nl + 1, nr)));
            if(nr + 1 < r)que.push(sec(nr + 1, r, even.get(nr + 1, r)));
        } else {
            vpos tmp = even.get(nl, r);
            ans.push_back(tmp.val);
            nr = tmp.pos;
            if(l < nl)que.push(sec(l, nl, odd.get(l, nl)));
            if(nl + 1 < nr)que.push(sec(nl + 1, nr, even.get(nl + 1, nr)));
            if(nr + 1 < r)que.push(sec(nr + 1, r, odd.get(nr + 1, r)));
        }
    }

    rep(i, N)cout << ans[i] << (i == N - 1 ? '\n' : ' ');
    return 0;

}

Measured memory_bytes: 82684