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;

#define x first
#define y second
#define int64 long long
#define MaxN 200000
#define Log 17

priority_queue <pair<int, pair<int, int>>> Queue;
int A[MaxN+1], B[MaxN+1], C[MaxN+1];
int rmq[2][Log+1][MaxN+1];
int P[MaxN+1];
int V[MaxN+1];
int N;

void Build(int l)
{
    int i, j;

    for(i = 1; i <= N; ++i)
    if(i % 2 == l) rmq[l][0][i] = i;

    for(i = 1; (1 << i) <= N; ++i)
        for(j = 1; j <= N - (1 << i) + 1; ++j)
            if(V[ rmq[l][i-1][j] ] < V[ rmq[l][i-1][j + (1 << i-1)] ]) rmq[l][i][j] = rmq[l][i-1][j];
            else rmq[l][i][j] = rmq[l][i-1][j + (1 << i-1)];
}

int getMin(int l, int a, int b)
{
    int k = P[b-a+1];

    if(V[ rmq[l][k][a] ] < V[ rmq[l][k][b - (1 << k) + 1] ]) return rmq[l][k][a];
    return rmq[l][k][b - (1 << k) + 1];
}

int main(){


    int i, x, y, st, dr, value;

    scanf("%d", &N);
    for(i = 1; i <= N; ++i) scanf("%d", &V[i]);
    for(i = 2; i <= N; ++i) P[i] = P[i/2] + 1;
    V[0] = N + 1;

    Build(0);
    Build(1);

    x = getMin(1, 1, N);
    Queue.push({-V[x], {1, N}});
    while(!Queue.empty())
    {
        st = Queue.top().y.x;
        dr = Queue.top().y.y;
        Queue.pop();

        x = getMin(st % 2, st, dr);
        y = getMin(dr % 2, x, dr);
        printf("%d %d ", V[x], V[y]);

        if(st < x){
            value = V[ getMin(st % 2, st, x - 1) ];
            Queue.push({-value, {st, x - 1}});
        }

        if(y - x > 1){
            value = V[ getMin(dr % 2, x + 1, y - 1) ];
            Queue.push({-value, {x + 1, y - 1}});
        }

        if(y < dr){
            value = V[ getMin(st % 2, y + 1, dr) ];
            Queue.push({-value, {y + 1, dr}});
        }
    }


return 0;
}