// tested by Hightail - https://github.com/dj3500/hightail
import std.stdio, std.string, std.conv, std.algorithm;
import std.range, std.array, std.math, std.typecons, std.container, core.bitop;

alias Itv = Tuple!(int, "v", int, "l", int, "r");
alias Pair = Tuple!(int, "v", int, "i");

int n;
int[] p;

void main() {
    scan(n);
    p = readln.split.to!(int[]);

    auto sg0 = SegTree(n), sg1 = SegTree(n);
    auto minh = new BinaryHeap!(Array!Itv, "a > b");

    foreach (i ; 0 .. n) {
        if (i & 1) {
            sg1.update(i, p[i]);
        }
        else {
            sg0.update(i, p[i]);
        }
    }

    minh.insert(Itv(sg0.getmin(0, n).v, 0, n));

    auto ans = new int[](n);

    foreach (i ; 0 .. n/2) {
        auto itv = minh.front; minh.popFront();

        Pair a, b;

        if (itv.l & 1) {
            a = sg1.getmin(itv.l, itv.r);
            b = sg0.getmin(a.i + 1, itv.r);
        }
        else {
            a = sg0.getmin(itv.l, itv.r);
            b = sg1.getmin(a.i + 1, itv.r);
        }

        ans[2*i] = a.v;
        ans[2*i + 1] = b.v;

        if (itv.l < a.i) {
            if (itv.l & 1) {
                minh.insert(Itv(sg1.getmin(itv.l, a.i).v, itv.l, a.i));
            }
            else {
                minh.insert(Itv(sg0.getmin(itv.l, a.i).v, itv.l, a.i));
            }
        }

        if (a.i + 1 < b.i) {
            if (itv.l & 1) {
                minh.insert(Itv(sg0.getmin(a.i + 1, b.i).v, a.i + 1, b.i));
            }
            else {
                minh.insert(Itv(sg1.getmin(a.i + 1, b.i).v, a.i + 1, b.i));
            }
        }

        if (b.i + 1 < itv.r) {
            if (itv.l & 1) {
                minh.insert(Itv(sg1.getmin(b.i + 1, itv.r).v, b.i + 1, itv.r));
            }
            else {
                minh.insert(Itv(sg0.getmin(b.i + 1, itv.r).v, b.i + 1, itv.r));
            }
        }

        debug {
            writefln("%(%s %)", ans);
        }
    }

    writefln("%(%s %)", ans);
}

struct SegTree {
    private {
        int N;
        int[] data;
        int[] idx;
        immutable inf = 1001001001;
    }

    this(int n) {
        N = 1; while (N < n) N *= 2;
        data = new int[](2*N - 1);
        idx = new int[](2*N - 1);
        data[] = inf;
        idx[] = -1;
        idx[N - 1 .. 2*N - 1] = iota(N).array();
    }

    void update(int i, int x) {
        i += N - 1;
        data[i] = x;

        while (i > 0) {
            i = (i - 1) / 2;

            if (data[2*i + 1] < data[2*i + 2]) {
                data[i] = data[2*i + 1];
                idx[i] = idx[2*i + 1];
            }
            else {
                data[i] = data[2*i + 2];
                idx[i] = idx[2*i + 2];
            }
        }
    }

    //alias Pair = Tuple!(int, "v", int, "i");

    Pair getmin(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r < 0) r = N;
        if (b <= l || r <= a) return Pair(inf, -1);
        if (a <= l && r <= b) return Pair(data[k], idx[k]);

        Pair v1 = getmin(a, b, 2*k + 1, l, l + (r - l) / 2);
        Pair v2 = getmin(a, b, 2*k + 2, l + (r - l) / 2, r);

        if (v1.v < v2.v) {
            return v1;
        }
        else {
            return v2;
        }
    }
}



void scan(T...)(ref T args) {
    string[] line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}


void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

Measured memory_bytes: 22704