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<cstdio>
#include<queue>
using namespace std;
const int maxn=200000,inf=0x3f3f3f3f;
int n,a[maxn+10];
struct mindata{
    int id,v;
    mindata(int id=0,int v=inf):
        id(id),v(v){}
};
mindata operator+(const mindata &a,const mindata &b){
    if(a.v<b.v) return mindata(a.id,a.v);
    else return mindata(b.id,b.v);
}
mindata c[maxn*5+10][3]; int sz;
void buildtree(){
    for(sz=1;sz<=n+1;sz<<=1);
    for(int i=sz+1;i<=sz+n;++i){
        scanf("%d",&a[i-sz]);
        for(int j=0;j<=1;++j) if(((i-sz)&1)==j)
            c[i][j]=mindata(i-sz,a[i-sz]);
        else c[i][j]=mindata();
        c[i][2]=mindata(i-sz,a[i-sz]);
    }
    for(int i=sz-1;i;--i)
        for(int j=0;j<=2;++j)
            c[i][j]=c[i<<1][j]+c[i<<1|1][j];
}
mindata query(int l,int r,int d){
    mindata ans;
    for(l+=sz-1,r+=sz+1;l^r^1;l>>=1,r>>=1){
        if(~l&1) ans=ans+c[l^1][d];
        if(r&1) ans=ans+c[r^1][d];
    }
    return ans;
}
struct heapnode{
    int l,r,x,y;
    heapnode(int l,int r):
        l(l),r(r){
            mindata v=query(l,r-1,l&1);
            x=v.id; y=query(v.id+1,r,~v.id&1).id;
        }
    bool operator<(const heapnode &t)const{
        if(a[x]!=a[t.x]) return a[x]>a[t.x];
        return a[y]>a[t.y];
    }
};
priority_queue<heapnode> heap;
int main(){
    scanf("%d",&n); buildtree();
    heap.push(heapnode(1,n));
    for(int i=1;i<=n>>1;++i){
        heapnode x=heap.top(); heap.pop();
        printf("%d %d ",a[x.x],a[x.y]);
        if(x.l<x.x) heap.push(heapnode(x.l,x.x-1));
        if(x.x<x.y-1) heap.push(heapnode(x.x+1,x.y-1));
        if(x.y<x.r) heap.push(heapnode(x.y+1,x.r));
    }
    return 0;
}