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;
int n;
const int N = 300000;
int P[N], Q[N];
int X[20][N];
int ask(int l, int r)
{
    int d = log2(r - l + 1);
    return (Q[X[d][l]] < Q[X[d][r - (1 << d) + 1]]? X[d][l]: X[d][r - (1 << d) + 1]);
}
int task(int l, int r)
{
    if (l & 1) return ask(l / 2 + 1, (r + 1) / 2) * 2 - 1;
    else return (ask(l / 2 + n / 2, r / 2 + n / 2) - n / 2) * 2;
}
vector <int> ans;
struct node
{
    int l, r, w;
};
int operator < (node a, node b) {return a.w > b.w;}
priority_queue <node> H;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> P[i];
    for (int i = 1; i <= n / 2; ++ i)
        Q[i] = P[i * 2 - 1], Q[i + n / 2] = P[i * 2];
    for (int i = 1; i <= n; ++ i) X[0][i] = i;
    for (int i = 1; i < 20; ++ i)
        for (int j = 1; j <= n; ++ j)
            X[i][j] = (Q[X[i - 1][j]] < Q[X[i - 1][j + (1 << (i - 1))]]? X[i - 1][j]: X[i - 1][j + (1 << (i - 1))]);

    H.push((node){1, n, P[task(1, n)]});
    while (!H.empty())
    {
        node t = H.top(); H.pop();
        int l = task(t.l, t.r), r = task(l + 1, t.r);
        ans.push_back(P[l]); ans.push_back(P[r]);
        if (t.l <= l - 1) H.push((node){t.l, l - 1, P[task(t.l, l - 1)]});
        if (l + 1 <= r - 1) H.push((node){l + 1, r - 1, P[task(l + 1, r - 1)]});
        if (r + 1 <= t.r) H.push((node){r + 1, t.r, P[task(r + 1, t.r)]});
    }
    for (int i = 0; i < ans.size(); ++ i) cout << ans[i] << ' ';
}