#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int INF = 1e9;
int n;
int p[500000];
vector<int> ans;

set<pair<pair<int, int>, pair<int, int> > > ss;

struct ii{
    int num, id;
};

ii min(ii a, ii b)
{
    if (a.num < b.num) return a;
    return b;
}

pair<ii, ii> tree[2000000];
int sw[2000000];

void build(int l, int r, int v)
{
    if (l + 1 == r)
    {
        if (l % 2 == 0)
            tree[v] = {{p[l], l}, {INF, l}};
        else
            tree[v] = {{INF, l}, {p[l], l}};
        return;
    }
    int m = (l + r) / 2;
    build(l, m, 2 * v + 1);
    build(m, r, 2 * v + 2);
    tree[v].first = min(tree[2 * v + 1].first, tree[2 * v + 2].first);
    tree[v].second = min(tree[2 * v + 1].second, tree[2 * v + 2].second);
}

void push(int v)
{
    if (sw[v])
    {
        sw[2 * v + 1] ^= 1;
        sw[2 * v + 2] ^= 1;
        swap(tree[2 * v + 1].first, tree[2 * v + 1].second);
        swap(tree[2 * v + 2].first, tree[2 * v + 2].second);
        sw[v] = 0;
    }
}

void change_parity(int l, int r, int v, int L, int R)
{
    if (R <= l || r <= L) return;
    if (L <= l && r <= R)
    {
        sw[v] ^= 1;
        swap(tree[v].first, tree[v].second);
        return;
    }
    int m = (l + r) / 2;
    push(v);
    change_parity(l, m, 2 * v + 1, L, R);
    change_parity(m, r, 2 * v + 2, L, R);
    tree[v].first = min(tree[2 * v + 1].first, tree[2 * v + 2].first);
    tree[v].second = min(tree[2 * v + 1].second, tree[2 * v + 2].second);
}

void change_int(int l, int r, int v, int P, int x)
{
    if (l + 1 == r)
    {
        if (l % 2) tree[v] = {{x, l}, {INF, l}};
        else tree[v] = {{INF, l}, {x, l}};
        if (sw[v]) swap(tree[v].first, tree[v].second); // should we check swaps here? // I don't know yet.
        return;
    }
    int m = (l + r) / 2;
    push(v);
    if (P < m) change_int(l, m, 2 * v + 1, P, x);
    else change_int(m, r, 2 * v + 2, P, x);
    tree[v].first = min(tree[2 * v + 1].first, tree[2 * v + 2].first);
    tree[v].second = min(tree[2 * v + 1].second, tree[2 * v + 2].second);
}

ii get_min(int l, int r, int v, int L, int R, int parity)
{
    if (R <= l || r <= L) return {INF, l};
    if (L <= l && r <= R)
    {
        //cout << l << " " << r << " : " << sw[v] << " " << tree[v].first.num << " " << tree[v].second.num << endl;
        // should we check swaps here? // No, we shouldn't.
        if (parity == 0)
        {
            return tree[v].first;
        }
        else
        {
            return tree[v].second;
        }
    }
    int m = (l + r) / 2;
    push(v);
    ii res = min(get_min(l, m, 2 * v + 1, L, R, parity), get_min(m, r, 2 * v + 2, L, R, parity));
    tree[v].first = min(tree[2 * v + 1].first, tree[2 * v + 2].first);
    tree[v].second = min(tree[2 * v + 1].second, tree[2 * v + 2].second);
    return res;
}

pair<int, int> get_opt(int L, int R)
{
    ii f = get_min(0, n, 0, L, R + 1, 0);
    int x = f.num;
    int idx = f.id;
    ii s = get_min(0, n, 0, idx + 1, R + 1, 1);
    int y = s.num;
    int idy = s.id;
    //cout << "? " << L << " " << R << " : " << x << " " << y << " (" << idx << ", " << idy << ")" << endl;
    return {x, y};
}

pair<ii, ii> get_opt2(int L, int R)
{
    ii f = get_min(0, n, 0, L, R + 1, 0);
    ii s = get_min(0, n, 0, f.id + 1, R + 1, 1);
    return {f, s};
}

void del(pair<int, int> lr)
{
    pair<ii, ii> a = get_opt2(lr.first, lr.second);
    int pos1 = a.first.id;
    int pos2 = a.second.id;

    int l1 = lr.first;
    int r1 = lr.second;

    change_parity(0, n, 0, pos1, pos2 + 1);
    change_int(0, n, 0, pos1, INF);
    change_int(0, n, 0, pos2, INF);

    if (l1 <= a.first.id - 1) ss.insert({get_opt(l1, a.first.id - 1), {l1, a.first.id - 1}});
    if (a.first.id + 1 <= a.second.id - 1) ss.insert({get_opt(a.first.id + 1, a.second.id - 1), {a.first.id + 1, a.second.id - 1}});
    if (a.second.id + 1 <= r1) ss.insert({get_opt(a.second.id + 1, r1), {a.second.id + 1, r1}});
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> p[i], p[i]--;
	build(0, n, 0);
	ss.insert({get_opt(0, n - 1), {0, n - 1}});
	while (ss.size())
    {
        pair<pair<int, int>, pair<int, int> > g = *ss.begin();
        ss.erase(ss.begin());
        ans.push_back(g.first.first);
        ans.push_back(g.first.second);
        del(g.second);
    }
    for (auto e : ans)
    {
        cout << e + 1 << " ";
    }
}


Measured memory_bytes: 20980