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;
typedef long long ll;
const int max_n=200005;
const int max_log=18;
const int inf=0x3f3f3f3f;
struct ST{
    int n,a[max_n];
    int lg[max_n],st[max_n][max_log+1];
    void init(int* _a,int _n){
        n=_n;
        for(int i=1;i<=n;i++)a[i]=_a[i];
        lg[1]=0;
        for(int i=2;i<=n;i++){
            lg[i]=lg[i-1];
            if(i==(i&-i))lg[i]++;
        }
        for(int i=1;i<=n;i++)st[i][0]=a[i];
        for(int j=1;j<=max_log;j++){
            for(int i=1;i+(1<<j)-1<=n;i++){
                st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
            }
        }
    }
    int query(int l,int r){
        if(l>r)return inf;
        int i=lg[r-l+1];
        return min(st[l][i],st[r-(1<<i)+1][i]);
    }
}Tree[2];
struct Node{
    int l,r,x;
    bool operator < (Node p)const{
        return x<p.x;
    }
};
int n,p[max_n];
int a[max_n];
int pos[max_n];
set<Node> s;
int ans[max_n],tot;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",p+i),pos[p[i]]=i;
    for(int j=0;j<2;j++){
        for(int i=1;i<=n;i++){
            if(i%2==j)a[i]=p[i];
            else a[i]=inf;
        }
        Tree[j].init(a,n);
    }
    s.insert({1,n,Tree[1&1].query(1,n)});
    while(!s.empty()){
        Node p=*s.begin();s.erase(p);
        int l=p.l,r=p.r,x=p.x;
        int y=Tree[(l+1)&1].query(pos[x]+1,r);
        //cout<<x<<' '<<y<<endl;
        ans[++tot]=x,ans[++tot]=y;
        x=pos[x],y=pos[y];
        if(x!=l)s.insert({l,x-1,Tree[l&1].query(l,x-1)});
        if(x+1<=y-1)s.insert({x+1,y-1,Tree[(x+1)&1].query(x+1,y-1)});
        if(y!=r)s.insert({y+1,r,Tree[(y+1)&1].query(y+1,r)});
    }
    for(int i=1;i<=tot;i++)printf("%d ",ans[i]);
    printf("\n");
    return 0;
}