#include <bits/stdc++.h>
using namespace std;
//#define int long long

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> plli;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()

const ll mod = 1e9 + 7;
const ll INF = 1<<30;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;

int size;
vector<int> node1((1 << 19) - 1);
vector<int> pos1((1 << 19) - 1);
vector<int> node2((1 << 19) - 1);
vector<int> pos2((1 << 19) - 1);

void init(int n_, vector<int>& node, vector<int>& pos) {
    size = 1;
    while (size < n_) size *= 2;
    for (int i = 0; i < 2 * size - 1; i++) node[i] = INT_MAX;
    for (int i = size - 1; i < 2 * size - 1; i++) pos[i] = i - (size - 1);
}

void update(int k, int a, vector<int>& node, vector<int>& pos) {
    k += size - 1;
    node[k] = a;
    while (k > 0){
        k = (k - 1) / 2;
        if (node[2 * k + 1] < node[2 * k + 2]) {
            node[k] = node[2 * k + 1];
            pos[k] = pos[2 * k + 1];
        }
        else {
            node[k] = node[2 * k + 2];
            pos[k] = pos[2 * k + 2];
        }
    }
}

pair<int, int> get_min(int queryL, int queryR, vector<int>& node, vector<int>& pos, int k = 0, int nodeL = 0, int nodeR = -1) {
    if (nodeR == -1) nodeR = size;
    if (nodeR <= queryL || queryR <= nodeL) return make_pair(INT_MAX, INT_MAX);
    if (queryL <= nodeL && nodeR <= queryR) return make_pair(node[k], pos[k]);
    else{
        int nodeM = (nodeL + nodeR) / 2;
        pair<int, int> vl = get_min(queryL, queryR, node, pos, 2 * k + 1, nodeL, nodeM);
        pair<int, int> vr = get_min(queryL, queryR, node, pos, 2 * k + 2, nodeM, nodeR);
        int val = INT_MAX; int min_pos = INT_MAX;
        if (vl.fi < vr.fi) {val = vl.fi; min_pos = vl.se;}
        else {val = vr.fi; min_pos = vr.se;}
        return make_pair(val, min_pos);
    }
}

int n;
int p[200000 + 5];
priority_queue<pair<pii, pii>, vector<pair<pii, pii>>, greater<pair<pii, pii>>> pq;
vector<int> ans;
bool used[200000 + 5];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    init(n, node1, pos1);
    init(n, node2, pos2);
    rep(i, n) {
        cin >> p[i];
        if (i % 2 == 0) update(i, p[i], node1, pos1);
        else update(i, p[i], node2, pos2);
    }
    pair<int, int> v1 = get_min(0, n, node1, pos1);
    update(v1.se, INT_MAX, node1, pos1);
    pair<int, int> v2 = get_min(v1.se + 1, n, node2, pos2);
    update(v2.se, INT_MAX, node2, pos2);
    pq.push(make_pair(make_pair(v1.fi, v2.fi), make_pair(0, v1.se)));
    pq.push(make_pair(make_pair(v1.fi, v2.fi), make_pair(v1.se + 1, v2.se)));
    pq.push(make_pair(make_pair(v1.fi, v2.fi), make_pair(v2.se + 1, n)));
    while (!pq.empty()) {
        pair<pii, pii> p = pq.top(); pq.pop();
        //if (p.fi.fi == INT_MAX || p.fi.se == INT_MAX) break;
        if (!used[p.fi.fi] && !used[p.fi.se]) {
            used[p.fi.fi] = true;
            used[p.fi.se] = true;
            ans.pb(p.fi.fi);
            ans.pb(p.fi.se);
        }
        int l = p.se.fi;
        int r = p.se.se;
        if (l == r) continue;
        pair<int, int> p1 = make_pair(INT_MAX, INT_MAX);
        pair<int, int> p2 = make_pair(INT_MAX, INT_MAX);
        if (l % 2 == 0) {
            p1 = get_min(l, r, node1, pos1);
            if (p1.se != INT_MAX) update(p1.se, INT_MAX, node1, pos1);
            p2 = get_min(p1.se + 1, r, node2, pos2);
            if(p2.se != INT_MAX) update(p2.se, INT_MAX, node2, pos2);
        }
        else {
            p1 = get_min(l, r, node2, pos2);
            if (p1.se != INT_MAX) update(p1.se, INT_MAX, node2, pos2);
            p2 = get_min(p1.se + 1, r, node1, pos1);
            if (p2.se != INT_MAX) update(p2.se, INT_MAX, node1, pos1);
        }
        //cout << p1.fi << " " << p2.fi << endl;
        if (p1.fi == INT_MAX || p2.fi == INT_MAX) continue;
        pq.push(make_pair(make_pair(p1.fi, p2.fi), make_pair(l, p1.se)));
        pq.push(make_pair(make_pair(p1.fi, p2.fi), make_pair(p1.se + 1, p2.se)));
        pq.push(make_pair(make_pair(p1.fi, p2.fi), make_pair(p2.se + 1, r)));
    }
    rep(i, n) cout << ans[i] << " " ;
    cout << endl;
}


Measured memory_bytes: 14448