#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <vector>
#include <queue>

#define MAXN 200050
#define INF 200000000

using namespace std;

priority_queue < pair < pair < int, int >, pair < int, int > > > q;
int n, A[MAXN], pos[MAXN];
pair < int, int > odd[4 * MAXN], even[4 * MAXN];
vector < pair < int, int > > od, ev;

pair < int, int > build(int idx, int l, int r, pair < int, int > *tree, vector < pair < int, int > > &who)
    {
    if(l == r)
    {
        tree[idx] = who[l];
        return tree[idx];
    }

    int mid = l + ((r - l) >> 1);
    tree[idx] = build(idx << 1, l, mid, tree, who);
    tree[idx] = min(tree[idx], build((idx << 1) + 1, mid + 1, r, tree, who));

    return tree[idx];
}

//int query(int idx, int l, int r, int wanted)
//{
//    if(r < wanted)      return INF;
//    if(l == r)
//    {
//        assert(l >= wanted and "BUGG!!");
//        int x = tree[idx];
//        tree[idx] = INF;
//        return x;
//    }
//
//    int mid = l + ((r - l) >> 1);
//
//
//    int ans = INF;
//    if(mid >= wanted)
//    {
//        if(tree[idx << 1] < tree[(idx << 1) + 1])
//            ans = query(idx << 1, l, mid, wanted);
//        else
//            ans = query((idx << 1) + 1, mid + 1, r, wanted);
//    }
//    else
//        ans = query((idx << 1) + 1, mid + 1, r, wanted);
//
//    tree[idx] = min(tree[idx << 1], tree[(idx << 1) + 1]);
//    return ans;
//}


pair < int, int > query(int idx, int l, int r, int linc, int rinc, pair < int, int > *tree)
{
    if(l >= linc and r <= rinc)
        return tree[idx];

    if(l > rinc or r < linc)
        return {INF, INF};

    int mid = l + ((r - l) >> 1);
    pair < int, int > x = query(idx << 1, l, mid, linc, rinc, tree);
    x = min(x, query((idx << 1) + 1, mid + 1, r, linc, rinc, tree));

    return x;
}

pair < int, int > get_range(int l, int r)
{
    if(l & 1)
    {
        assert(!(r & 1) and "REVERSE PARITY EVEN");

        pair < int, int > x = query(1, 0, od.size() - 1, l/2, r/2 - 1, odd);
        pair < int, int > y = query(1, 0, ev.size() - 1, x.second/2+1, r/2, even);

        return {x.first, y.first};
    }
    else
    {
        assert((r & 1) and "REVERSE PARITY ODD");

        pair < int, int > x = query(1, 0, ev.size() - 1, l/2, r/2, even);
        pair < int, int > y = query(1, 0, od.size() - 1, x.second/2, r/2, odd);

        return {x.first, y.first};
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 0;i < n;++i)
    {
        scanf("%d", A + i);
        if(!(i & 1))
            ev.push_back({A[i], i});

        else
            od.push_back({A[i], i});

        pos[A[i]] = i;
    }

    build(1, 0, ev.size() - 1, even, ev);
    build(1, 0, od.size() - 1, odd, od);

    pair < int, int > x = get_range(0, n - 1);
    q.push({{-x.first, -x.second}, {0, n - 1}});

    while(!q.empty())
    {
        int a = -q.top().first.first;
        int b = -q.top().first.second;

        int l = q.top().second.first;
        int r = q.top().second.second;

        q.pop();

        assert(l < r and "BUGG!!!");

        printf("%d %d ", a, b);

        if(l + 1 < pos[a])
        {
            x = get_range(l, pos[a] - 1);
            q.push({{-x.first, -x.second}, {l, pos[a] - 1}});
        }
        if(pos[b] + 1 < r)
        {
            x = get_range(pos[b] + 1, r);
            q.push({{-x.first, -x.second}, {pos[b] + 1, r}});
        }
        if(pos[a] + 1 < pos[b])
        {
            x = get_range(pos[a] + 1, pos[b] - 1);
            q.push({{-x.first, -x.second}, {pos[a] + 1, pos[b] - 1}});
        }
    }
    return 0;
}


Measured memory_bytes: 13804