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;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MAX=1<<17;
const int INF=0x3f3f3f3f;
int N,p[2*MAX],seg[2][2*MAX],invp[2*MAX],ans[2*MAX],anscnt;
int build(int *arr,int x){
    if(x>=MAX) {
        if(x-MAX<N/2) return arr[x];
        return INF;
    }
    return arr[x]=min(build(arr,x*2),build(arr,x*2+1));
}
int find_min(int *arr,int x,int y,int a,int b,int p){
    if(x<=a&&b<=y) return arr[p];
    if(x>=b||y<=a) return INF;
    return min(find_min(arr,x,y,a,(a+b)/2,2*p),find_min(arr,x,y,(a+b)/2,b,2*p+1));
}
struct range{
    int x,y;
    int r_min1,r_min2,r_idx1,r_idx2;
    void r_gen(int a,int b){
        x=a,y=b;
        if(a>=b) return;
        r_min1=find_min(seg[x%2],x/2,y/2,0,MAX,1);
        r_idx1=invp[r_min1];
        //printf("%d %d %d %d %d %d\n",x,y,r_min1,r_idx1,(r_idx1+1)/2,(y+1)/2);
        r_min2=find_min(seg[!(x%2)],(r_idx1+1)/2,(y+1)/2,0,MAX,1);
        r_idx2=invp[r_min2];
    }
    bool operator<(const range &a)const{
        return r_min1>a.r_min1;
    }
};
priority_queue<range> atl;
int main(){
    range tmp;
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&p[i]),invp[p[i]]=i;
    for(int i=0;i<N;i++) seg[i%2][MAX+i/2]=p[i];
    build(seg[0],1),build(seg[1],1);
    tmp.r_gen(0,N);
    atl.push(tmp);
    while(!atl.empty()){
        range t=atl.top();
        atl.pop();
        if(t.y>t.x){
            ans[anscnt++]=t.r_min1;
            ans[anscnt++]=t.r_min2;
            tmp.r_gen(t.x,t.r_idx1); atl.push(tmp);
            tmp.r_gen(t.r_idx1+1,t.r_idx2); atl.push(tmp);
            tmp.r_gen(t.r_idx2+1,t.y); atl.push(tmp);
        }
    }
    for(int i=0;i<N;i++) printf("%d ",ans[i]);
    printf("\n");
}