#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;

const int MAXN = 2 * 100000, INF = 1000 * 1000 * 1000;
int a[2 * MAXN + 1], n, q[2 * MAXN + 1];
pair<int, int> t[4 * MAXN + 1][4];
bool ff;

void build(int v = 1, int l = 1, int r = n) {
    if(l == r) {
        t[v][0] = { a[l], l };
        t[v][1] = { l & 1 ? a[l] : INF, l };
        t[v][2] = { l % 2 == 0 ? a[l] : INF, l };
    }
    else {
        int m = (l + r) / 2;
        build(v * 2, l, m);
        build(v * 2 + 1, m + 1, r);
        for(int sh = 0; sh < 3; sh++)
            t[v][sh] = min(t[v * 2][sh], t[v * 2 + 1][sh]);
    }
}

void upd(int pos, int val, int v = 1, int l = 1, int r = n) {
    if(l == r) {
        t[v][0] = { val, l };
        t[v][1] = { val, l };
        t[v][2] = { val, l };
    }
    else {
        int m = (l + r) / 2;
        if(pos <= m)
            upd(pos, val, v * 2, l, m);
        else
            upd(pos, val, v * 2 + 1, m + 1, r);
        for(int sh = 0; sh < 3; sh++)
            t[v][sh] = min(t[v * 2][sh], t[v * 2 + 1][sh]);
    }
}

pair<int, int> getVal(int sh, int l, int r, int tv = 1, int tl = 1, int tr = n) {
    if(l > r)
        return { INF, INF };
    else if(l == tl && r == tr) {
        return t[tv][sh];
    }
    else {
        int tm = (tl + tr) / 2;
        pair<int, int> res1 = getVal(sh, l, min(tm, r), tv * 2, tl, tm);
        pair<int, int> res2 = getVal(sh, max(tm + 1, l), r, tv * 2 + 1, tm + 1, tr);
        return min(res1, res2);
    }
}

int get(vector<int>& res, int pos) {
    if(pos >= (int)res.size())
        return INF;
    return res[pos];
}

vector<int> vec;

pair<int, int> calc(int l, int r) {
    int p1 = getVal((l & 1) ? 1 : 2, l, r - 1).second;
    int p2 = getVal((p1 & 1) ? 2 : 1, p1 + 1, r).second;
    return { p1, p2 };
}

void solve(int l, int r) {
    set<pair<int, pair<int, int> > > s;
    s.insert({ a[calc(1, n).first], { 1, n } });
    while(!s.empty()) {
        l = s.begin()->second.first;
        r = s.begin()->second.second;
        int p1 = calc(l, r).first;
        int p2 = calc(l, r).second;
        vec.push_back(a[p1]);
        vec.push_back(a[p2]);
        s.erase(s.begin());
        assert((r - l + 1) % 2 == 0);
        upd(p1, INF);
        upd(p2, INF);
        if (l < p1 - 1)
            s.insert({ a[calc(l, p1 - 1).first], { l, p1 - 1} });
        if(p1 + 1 < p2 - 1)
            s.insert({ a[calc(p1 + 1, p2 - 1).first], { p1 + 1, p2 - 1 } });
        if(p2 + 1 < r)
            s.insert({ a[calc(p2 + 1, r).first], { p2 + 1, r } });
    }
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    cin >> n;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    build();
    solve(1, n);
    for(auto x: vec)
        printf("%d ", x);
    printf("\n");
    return 0;
}

Measured memory_bytes: 25972