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 + 11;
struct ddd{
    int l, r, fl, mi;
    bool operator < (const ddd &x) const{
        return mi > x.mi;
    }
};
priority_queue<ddd> q;
int f[2][N][21], n, a[N], pos[N], lg[N];
int ans[N], tot;
int find(int fl, int l, int r){
    int len = lg[r - l + 1];
    return min(f[fl][l][len], f[fl][r - (1 << len) + 1][len]);
}
int main(){
    cin>>n;
    memset(f, 127, sizeof(f));
    for(int i = 1;i <= n; i++){
        scanf("%d", &a[i]);
        int fl = i & 1;
        f[fl][i][0] = a[i];
        pos[a[i]] = i;
    }
    for(int i = 2;i <= 2e5; i++){
        lg[i] = lg[i>>1] + 1;
    }
    for(int j = 0;j <= 19; j++){
        for(int i = 1;i <= n; i++){
            if(i + (1 << j) > n)break;
            f[0][i][j+1] = min(f[0][i][j], f[0][i + (1 << j)][j]);
            f[1][i][j+1] = min(f[1][i][j], f[1][i + (1 << j)][j]);
        }
    }
    ddd now = (ddd){1, n, 1, find(1, 1, n)};
    q.push(now);
    int x, y;
    while(q.size()){
        now = q.top();
        q.pop();
        x = now.mi;
        y = find(now.fl ^ 1, pos[x] + 1, now.r);
        ans[++tot] = x; ans[++tot] = y;
        if(pos[x] > now.l)q.push((ddd){now.l, pos[x] - 1, now.fl, find(now.fl, now.l, pos[x] - 1)});
        if(pos[x] + 1 < pos[y] - 1)q.push((ddd){pos[x] + 1, pos[y] - 1, now.fl ^ 1, find(now.fl ^ 1, pos[x] + 1, pos[y] - 1)});
        if(pos[y] + 1 < now.r)q.push((ddd){pos[y] + 1, now.r, now.fl, find(now.fl, pos[y] + 1, now.r)});
    }
    for(int i = 1;i <= n; i++){
        printf("%d ", ans[i]);
    }
    puts("");
    return 0;
}