#include <stdio.h>
#include <bits/stdc++.h>
     
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = l; i < r; i++)
#define repb(i, r, l) for (int i = r; i > l; i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)

using namespace std;

const int N = 200000;
const int inf = (int)1e9 + 1;
const ll big = (ll)1e18 + 1;
const int P = 239;
const int MOD = (int)1e9 + 7;
const int MOD1 = (int)1e9 + 9;
const double eps = 1e-6;
const double pi = atan2(0, -1);
const int ABC = 26;

struct node
{
    int pr, cnt;
    pair<int, int> v, maxv;
    node *L, *R;
    node(pair<int, int> v) { pr = rand() << 15 | rand(); this->v = maxv = v; cnt = 1; L = R = NULL; }
};

pair<int, int> get_maxv(node *t) { return t != NULL ? t->maxv : mp(-1, -1); }

void upd_maxv(node *t) { if (t != NULL) t->maxv = max(max(get_maxv(t->L), t->v), get_maxv(t->R)); }

int get_cnt(node *t) { return t != NULL ? t->cnt : 0; }

void upd_cnt(node *t) { if (t != NULL) t->cnt = get_cnt(t->L) + 1 + get_cnt(t->R); }

pair<node*, node*> split(node *t, int x)
{
    if (t == NULL)
        return {NULL, NULL};
    else if (get_cnt(t->L) >= x)
    {
        auto p = split(t->L, x);
        t->L = p.se;
        upd_cnt(t); upd_maxv(t);
        p.se = t;
        return p;
    }
    else
    {
        auto p = split(t->R, x - get_cnt(t->L) - 1);
        t->R = p.fi;
        upd_cnt(t); upd_maxv(t);
        p.fi = t;
        return p;
    }
}

node* merge(node *l, node *r)
{
    if (l == NULL)
        return r;
    else if (r == NULL)
        return l;
    else if (l->pr <= r->pr)
    {
        l->R = merge(l->R, r);
        upd_cnt(l); upd_maxv(l);
        return l;
    }
    else
    {
        r->L = merge(l, r->L);
        upd_cnt(r); upd_maxv(r);
        return r;
    }
}

int get_pos(node *t, pair<int, int> p)
{
    if (t == NULL)
        return 0;
    else if (get_maxv(t->L) > p)
        return get_pos(t->L, p);
    else if (t->v > p)
        return get_cnt(t->L);
    else
        return get_cnt(t->L) + 1 + get_pos(t->R, p);
}

void get_order(node *t, vector<pair<int, int> > &order)
{
    if (t == NULL)
        return;
    get_order(t->L, order);
    order.push_back(t->v);
    get_order(t->R, order);
}

node* merge_1(node *l, node *r)
{
    if (get_cnt(l) < get_cnt(r))
        swap(l, r);
    vector<pair<int, int> > order;
    get_order(r, order);
    vector<node*> parts;
    parts.push_back(l);
    int last = 0;
    for (auto it : order)
    {
        int cnt = get_pos(parts[last], it);
        auto p = split(parts[last], cnt);
        parts[last] = p.fi;
        parts.push_back(new node(it));
        parts.push_back(p.se);
        last = sz(parts) - 1;
    }
    l = NULL;
    rep(i, 0, sz(parts))
        l = merge(l, parts[i]);
    return l;
}

int a[N];
int pos[N];
int log_2[N + 1];
int st_0[18][N], st_1[18][N];

void build(int n)
{
    n /= 2;
    log_2[1] = 0;
    rep(i, 1, n + 1)
        if ((1 << (log_2[i - 1] + 1)) <= i)
            log_2[i] = log_2[i - 1] + 1;
        else
            log_2[i] = log_2[i - 1];
    int sz = 0;
    while ((1 << sz) <= n)
        sz++;
    rep(i, 0, n)
        st_0[0][i] = a[i * 2];
    rep(j, 1, sz)
        rep(i, 0, n - (1 << j) + 1)
            st_0[j][i] = min(st_0[j - 1][i], st_0[j - 1][i + (1 << (j - 1))]);
    rep(i, 0, n)
        st_1[0][i] = a[i * 2 + 1];
    rep(j, 1, sz)
        rep(i, 0, n - (1 << j) + 1)
            st_1[j][i] = min(st_1[j - 1][i], st_1[j - 1][i + (1 << (j - 1))]);
}

int get_0(int l, int r)
{
    int len = log_2[r - l];
    return min(st_0[len][l], st_0[len][r - (1 << len)]);
}

int get_1(int l, int r)
{
    int len = log_2[r - l];
    return min(st_1[len][l], st_1[len][r - (1 << len)]);
}

int find_best(int l, int r)
{
    if (l % 2 == 0)
        return pos[get_0(l / 2, r / 2)];
    else
        return pos[get_1(l / 2, r / 2)];
}

node* solve(int l, int r)
{
    if (l == r)
        return NULL;
    int x = find_best(l, r);
    int y = find_best(x + 1, r + 1);
    node* res = NULL;
    res = merge_1(res, solve(l, x));
    res = merge_1(res, solve(x + 1, y));
    res = merge_1(res, solve(y + 1, r));
    res = merge(new node({a[x], a[y]}), res);
    return res;
}

int main()
{
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(20);
    cout << fixed;
    //ll TL = 1.95 * CLOCKS_PER_SEC;
    //clock_t time = clock();
    int n;
    cin >> n;
    rep(i, 0, n)
        a[i] = i + 1;
    rep(i, 0, n)
    {
        cin >> a[i];
        a[i]--;
        pos[a[i]] = i;
    }
    build(n);
    node* ans = solve(0, n);
    vector<pair<int, int> > order;
    get_order(ans, order);
    for (auto it : order)
        cout << it.fi + 1 << " " << it.se + 1 << " ";
    cout << "\n";
    return 0;
}

Measured memory_bytes: 63660