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;
using pii = pair<int,int>;

struct seg_tr{
    const static int MAX=1<<18;
    int tr[MAX<<1];
    void init(int n,int *arr) {
        for(int i=0;i<n;i++) tr[i+MAX]=arr[i];
        for(int i=MAX-1;i;i--) tr[i]=min(tr[i*2],tr[i*2+1]);
    }
    int get(int l,int r) {
        l+=MAX;r+=MAX;
    
        int mx=MAX;
        while(l<=r){
            mx=min({mx,tr[l],tr[r]});
            if(l&1)l++; if(!(r&1)) r--;
            l>>=1; r>>=1;
        }
        return mx;
    }
}tr[2];

int n,arr[200000],tmp[200000],pos[200001];
vector<int> ans;

struct td{
    int l,r,v[2];
    bool operator<(const td &rhs)const {
        return v[0]>rhs.v[0];
    }
};

bool make(int l,int r,td &v) {
    if(l>r) return false;

    v.v[0] = tr[l%2].get(l/2,(r-l%2)/2);
    
    int li=(pos[v.v[0]]+1)/2;
    v.v[1]=tr[(l%2)^1].get(li,r/2);
    v.l=l; v.r=r;
    return true;
}
int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",arr+i);
    for(int i=0;i<n;i++) pos[arr[i]]=i;
    
    for(int s=0;s<2;s++) {
        for(int i=0;i<n/2;i++) tmp[i]=arr[i*2+s];
        tr[s].init(n/2,tmp);
    }
    
    priority_queue<td> que;
    td tmp;
    make(0,n-1,tmp);
    que.push(tmp);
    while(!que.empty()) {
        td cur=que.top();que.pop();
        ans.push_back(cur.v[0]);
        ans.push_back(cur.v[1]);

        if(make(cur.l,pos[cur.v[0]]-1,tmp)) que.push(tmp);
        if(make(pos[cur.v[0]]+1,pos[cur.v[1]]-1,tmp)) que.push(tmp);
        if(make(pos[cur.v[1]]+1,cur.r,tmp)) que.push(tmp);
    }
    for(auto &it:ans) printf("%d ",it);
    
    return 0;
}