Problem: Let N be a positive even number.

We have a permutation of (1, 2, ..., N), p = (p_1, p_2, ..., p_N). Snuke is constructing another permutation of (1, 2, ..., N), q, following the procedure below.

First, let q be an empty sequence. Then, perform the following operation until p becomes empty:

* Select two adjacent elements in p, and call them x and y in order. Remove x and y from p (reducing the length of p by 2), and insert x and y, preserving the original order, at the beginning of q.



When p becomes empty, q will be a permutation of (1, 2, ..., N).

Find the lexicographically smallest permutation that can be obtained as q.

Constraints

* N is an even number.
* 2 ≤ N ≤ 2 × 10^5
* p is a permutation of (1, 2, ..., N).

Input

Input is given from Standard Input in the following format:


N
p_1 p_2 ... p_N


Output

Print the lexicographically smallest permutation, with spaces in between.

Examples

Input

4
3 2 4 1


Output

3 1 2 4


Input

2
1 2


Output

1 2


Input

8
4 6 3 2 8 5 7 1


Output

3 1 2 7 4 6 8 5

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+9;
const int INF = 0x3f3f3f3f;

int a[2][N], pos[N], d[2][N][32];

struct Node {
    int p, l, r;
    bool operator < (const Node& rhs) const {
        return p > rhs.p;
    }
};

void initRMQ(int n, int pa) {
    for (int i = 0; i < n; i++) d[pa][i][0] = a[pa][i];
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 0; i + (1 << j) - 1 < n; i++) {
            d[pa][i][j] = min(d[pa][i][j - 1], d[pa][i + (1 << (j - 1))][j - 1]);
        }
    }
}

int RMQ(int l, int r, int pa) {
    int k = 0;
    while ((1 << (k + 1)) <= r - l + 1) k++;
    return min(d[pa][l][k], d[pa][r - (1 << k) + 1][k]);
}


int main() {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        int p; cin >> p;
        a[i & 1][i] = p;
        a[(i & 1) ^ 1][i] = INF;
        pos[p] = i;
    }
    initRMQ(n, 0);
    initRMQ(n, 1);
    priority_queue<Node> q;
    int x = RMQ(0, n - 1, 0);
    q.push( {x, 0, n - 1} );
    while (!q.empty()) {
        Node u = q.top();
        q.pop();
        int v1 = u.p;
        int v2 = RMQ(pos[u.p] + 1, u.r, (pos[u.p] & 1) ^ 1);
        cout << v1 << " " << v2 << " ";
        v1 = pos[v1];
        v2 = pos[v2];
        if (u.l != v1) q.push( {RMQ(u.l, v1 - 1, u.l & 1), u.l, v1 - 1} );
        if (v1 + 1 != v2) q.push( {RMQ(v1 + 1, v2 - 1, (v1 + 1) & 1), v1 + 1, v2 - 1} );
        if (v2 != u.r) q.push( {RMQ(v2 + 1, u.r, (v2 + 1) & 1), v2 + 1, u.r} );
    }
    return 0;
}