#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
#include <bits/stdc++.h>

using std::cerr;
using std::cin;
using std::cout;

using std::abs;
using std::min;
using std::max;
using std::swap;

using std::map;
using std::pair;
using std::set;
using std::string;
using std::vector;

using ll = long long;
using uint = unsigned int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define ff first
#define ss second
#define pb emplace_back
#define sqr(x) ((x) * (x))
#ifdef LOCAL
#define dbg(as...) {\
    vector<string> _v; \
    std::stringstream _ss(#as);\
    string _cur, _loc;\
    while (getline(_ss, _cur, ',')) {\
        while (count(_cur.begin(), _cur.end(), '(') != count(_cur.begin(), _cur.end(), ')')) {\
            getline(_ss, _loc, ',');\
            _cur += "," + _loc;\
        }\
    _v.pb(_cur);\
    }\
    err(_v.begin(), as);\
}
#else
#define dbg(as...)
#endif

template<typename T>
void err(vector<string>::iterator it, T a) {
    cerr << it->substr((*it)[0] == ' ') << " = " << a << '\n';
}
template<typename T, typename...Ts>
void err(vector<string>::iterator it, T a, Ts...as) {
    cerr << it->substr((*it)[0] == ' ') << " = " << a << ", ";
    err(++it, as...);
}

struct init {
    init() {
        cin.tie(0);
        std::iostream::sync_with_stdio(0);
        cout << std::fixed << std::setprecision(10);
        cerr << std::fixed << std::setprecision(10);
        #ifdef LOCAL
        srand(300); 
        #else
        srand(time(0));
        #endif
    }
    ~init() {
        #ifdef LOCAL
        cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC << "s.\n";
        #endif
    }
} init;

const int MAXN = 2e5;
const pii INF = {1e9, 1e9};
struct node {
    pii x, mn; // {val, ind}
    int y;
    node * left = nullptr, * right = nullptr;
    node() {}
    node(pii _x) : x(_x), mn(_x), y(rand()) {}
} nodes[MAXN];
int ffr = 0;
typedef node * pnode;

void update(pnode v) {
    if (!v) return;
    v->mn = min({v->left ? v->left->mn : INF, v->right ? v->right->mn : INF, v->x});
}

pnode merge(pnode left, pnode right) {
    if (!left) return right;
    if (!right) return left;
    if (left->y > right->y) {
        left->right = merge(left->right, right);
        update(left);
        return left;
    } else {
        right->left = merge(left, right->left);
        update(right);
        return right;
    }
}

pair<pnode, pnode> split(pnode tree, int x) {
    if (!tree) return {tree, tree};
    if (tree->x.ss > x) {
        auto tmp = split(tree->left, x);
        tree->left = tmp.ss;
        update(tree);
        return {tmp.ff, tree};
    } else {
        auto tmp = split(tree->right, x);
        tree->right = tmp.ff;
        update(tree);
        return {tree, tmp.ss};
    }
}

pnode pushback(pnode tree, pii x) {
    pnode xptr = &(nodes[ffr++] = node(x));
    return merge(tree, xptr);
}

vector<int> g[MAXN];
vector<pii> ps;

int build(pnode even, pnode odd) {
    int num = ps.size();
    // dbg(num);
    pii mne = even->mn;
    auto tmp_odd = split(odd, mne.ss);
    pii mno = tmp_odd.ss->mn;
    
    ps.pb(mne.ff, mno.ff);
    auto tmp_odd2 = split(tmp_odd.ss, mno.ss);
    auto tmp_odd3 = split(tmp_odd2.ff, mno.ss - 1);

    auto odd1 = tmp_odd.ff;
    auto odd2 = tmp_odd3.ff;
    auto odd3 = tmp_odd2.ss;

    auto tmp_even = split(even, mne.ss);
    auto tmp_even2 = split(tmp_even.ff, mne.ss - 1);
    auto tmp_even3 = split(tmp_even.ss, mno.ss);

    auto even1 = tmp_even2.ff;
    auto even2 = tmp_even3.ff;
    auto even3 = tmp_even3.ss;

    if (even1) 
        g[num].pb(build(even1, odd1));
    if (even2) 
        g[num].pb(build(odd2, even2));
    if (even3) 
        g[num].pb(build(even3, odd3));

    return num;
}

struct comp{
    bool operator()(const int & p1, const int & p2) { 
        return ps[p1] < ps[p2];
    }
};

int main() {

    pnode even = nullptr, odd = nullptr;
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (i & 1)
            odd = pushback(odd, {x, i});
        else
            even = pushback(even, {x, i});
    }

    build(even, odd);

    set<int, comp> s;
    s.insert(0);
    vector<int> ans;

    while (!s.empty()) {
        int v = *s.begin();
        s.erase(s.begin());
        ans.pb(ps[v].ff);
        ans.pb(ps[v].ss);
        for (int to : g[v])
            s.insert(to);
    }

    for (int i : ans) cout << i << ' ';
    cout << '\n';

    return 0;
}


Measured memory_bytes: 31348