#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#include <functional>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<ll, ll, ll, ll> tlglglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
typedef vector<ll> vll;
typedef vector< vector<ll> > matrix;
typedef unsigned int uint;
typedef unsigned long long ull;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
template <class T> using VVV = V<VV<T>>;
#define REP(i, x, y) for(ll i = (ll)x; i < (ll)y; i++)
#define DREP(i, x, y, d) for(ll i = (ll)x; i < (ll)y; i += (ll)d)
#define PER(i, x, y) for(ll i = (ll)x; i > (ll)y; i--)
#define DPER(i, x, y, d) for(ll i = (ll)x; i > (ll)y; i -= (ll)d)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-12;
void yesno(bool ok, string yes = "Yes", string no = "No") {
    if (ok) {
        cout << yes << endl;
    } else {
        cout << no << endl;
    }
}

// abstruct segment tree 抽象化セグメント木(非再帰)
// https://beet-aizu.github.io/library/library/segtree/basic/ushi.cpp.html
template <typename T>
struct segtree{
    using F = function<T(T,T)>;
    int n;
    F f;
    T ti;
    vector<T> dat;

    segtree(){}
    segtree(F f, T ti): f(f), ti(ti){}

    void init(int n_) {
        n = 1;
        while (n < n_) {
            n <<= 1;
        }
        dat.assign(n << 1, ti);
    }

    void build(const vector<T> &v) {
        int n_ = v.size();
        init(n_);
        for (int i = 0; i < n_; i++) {
            dat[n + i] = v[i];
        }
        for (int i = n - 1; i > 0; i--) {
            dat[i] = f(dat[i << 1], dat[(i << 1) | 1]);
        }
    }

    void set_val(int k, T x) {
        k += n;
        dat[k] = x;
        while (k >>= 1) {
            dat[k] = f(dat[k << 1],dat[(k << 1) | 1]);
        }
    }

    // [a, b)の範囲の情報を得る
    T query(int a, int b) {
        if (a >= b) {
            return ti;
        }
        T vl = ti, vr = ti;
        for (int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                vl = f(vl, dat[l]);
                l++;
            }
            if (r & 1) {
                r--;
                vr = f(dat[r], vr);
            }
        }
        return f(vl, vr);
    }

    template<typename C>
    int find(int st, C &check, T &acc, int k, int l, int r) {
        if(l + 1 == r){
            acc = f(acc, dat[k]);
            return check(acc) ? k-n : -1;
        }
        int m = (l + r) >> 1;
        if (m <= st) {
            return find(st, check, acc, (k << 1) | 1, m, r);
        }
        if (st <= l && !check(f(acc, dat[k]))) {
            acc = f(acc, dat[k]);
            return -1;
        }
        int vl = find(st, check, acc, k << 1, l, m);
        if (~vl) {
            return vl;
        }
        return find(st, check, acc, (k << 1) | 1, m, r);
    }

    // セグ木上の2分探索
    template<typename C>
    int find(int st, C &check){
        T acc = ti;
        return find(st, check, acc, 1, 0, n);
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    V<plglg> peven(N);
    V<plglg> podd(N);
    REP(i, 0, N) {
        ll v;
        cin >> v;
        if (i % 2 == 0) {
            peven[i] = plglg(v, i);
            podd[i] = plglg(inf, i);
        } else {
            peven[i] = plglg(inf, i);
            podd[i] = plglg(v, i);
        }
    }
    auto f = [](plglg a, plglg b) {
        if (a < b) {
            return a;
        } else {
            return b;
        }
    };
    segtree<plglg> segeven(f, plglg(inf, 0));
    segeven.build(peven);
    segtree<plglg> segodd(f, plglg(inf, 0));
    segodd.build(podd);
    priority_queue<tlglglglg, V<tlglglglg>, greater<tlglglglg>> que;
    plglg segp = segeven.query(0, N);
    que.push(tlglglglg(segp.first, segp.second, 0, N));
    vll ans;
    REP(i, 0, N / 2) {
        tlglglglg t = que.top();
        que.pop();
        ll val = get<0>(t);
        ll ind = get<1>(t);
        ll left = get<2>(t);
        ll right = get<3>(t);
        // cout << val << " " << ind << " " << left << " " << right << " ";
        ans.push_back(val);
        if (left % 2 == 0) {
            plglg sec = segodd.query(ind + 1, right);
            // cout << sec.first << " " << sec.second << endl;
            ans.push_back(sec.first);
            if (ind != left) {
                plglg segval = segeven.query(left, ind);
                que.push(tlglglglg(segval.first, segval.second, left, ind));
            }
            if (ind + 1 != sec.second) {
                plglg segval = segodd.query(ind + 1, sec.second);
                que.push(tlglglglg(segval.first, segval.second, ind + 1, sec.second));
            }
            if (sec.second + 1 != right) {
                plglg segval = segeven.query(sec.second + 1, right);
                que.push(tlglglglg(segval.first, segval.second, sec.second + 1, right));
            }
        } else {
            plglg sec = segeven.query(ind + 1, right);
            // cout << sec.first << " " << sec.second << endl;
            ans.push_back(sec.first);
            if (ind != left) {
                plglg segval = segodd.query(left, ind);
                que.push(tlglglglg(segval.first, segval.second, left, ind));
            }
            if (ind + 1 != sec.second) {
                plglg segval = segeven.query(ind + 1, sec.second);
                que.push(tlglglglg(segval.first, segval.second, ind + 1, sec.second));
            }
            if (sec.second + 1 != right) {
                plglg segval = segodd.query(sec.second + 1, right);
                que.push(tlglglglg(segval.first, segval.second, sec.second + 1, right));
            }
        }
    }
    REP(i, 0, N) {
        cout << ans[i] << " ";
    }
    cout << endl;
}


Measured memory_bytes: 27248