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>
#define pb push_back
#define fi first
#define se second
#define CLR(A, X) memset(A, X, sizeof(A))
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
const double eps = 1e-10;
int dcmp(double x) { if(fabs(x) < eps) return 0; return x>0?1:-1; }
const LL MOD = 1e9+7;
const int N = 2e5+5;
const int INF = 0x3f3f3f3f;

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

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

int RMQ(int L, int R, int v) {
    int k = 0;
    while((1<<(k+1)) <= R-L+1) k++;
    return min(d[v][L][k], d[v][R-(1<<k)+1][k]);
}

struct node {
    int x, L, R;
    bool operator < (const node& A) const {
        return x > A.x;
    }
};

int main() {
    int n, x;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &x);
        a[i&1][i] = x;
        a[(i&1)^1][i] = INF;
        pos[x] = i;
    }
    RMQ_init(n, 0); RMQ_init(n, 1);
    priority_queue<node> Q;
    x = RMQ(0, n-1, 0);
    //cout<<x<<endl;
    Q.push({x, 0, n-1});
    while(!Q.empty()) {
        node x = Q.top(); Q.pop();
        int v1 = x.x, v2 = RMQ(pos[x.x]+1, x.R, (pos[x.x]&1)^1);
        printf("%d %d ", v1, v2);
        v1 = pos[v1], v2 = pos[v2];
        if(x.L != v1) Q.push({RMQ(x.L, v1-1, x.L&1), x.L, v1-1});
        if(v1+1 != v2) Q.push({RMQ(v1+1, v2-1, (v1+1)&1), v1+1, v2-1});
        if(v2 != x.R) Q.push({RMQ(v2+1, x.R, (v2+1)&1), v2+1, x.R});
    }
    return 0;
}