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>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)

const int INF = 1e9 + 7;

struct segtree{
    static const int SEG=1<<18;
    vector<P> dat;
    segtree():dat(SEG*2, P(INF,INF)){}
    void update(int k, P p){
        k+=SEG-1;
        dat[k]=p;
        while(k){
            k=(k-1)/2;
            dat[k]=min(dat[k*2+1],dat[k*2+2]);
        }
    }
    P query(int a,int b,int k=0,int l=0,int r=SEG){
        if(r<=a||b<=l)return P(INF,INF);
        if(a<=l&&r<=b)return dat[k];
        return min(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r));
    }
};

int n;
int p[200005];
 
segtree odd,even;
 
typedef tuple<P,P,P> T;

T calc(int l, int r) {
    int ll, rr;
    if (l%2 == 1) {
        ll = odd.query(l,r).second;
        rr = even.query(ll,r).second;
    } else {
        ll = even.query(l,r).second;
        rr = odd.query(ll,r).second;
    }
    return T({p[ll], p[rr]}, {ll,rr}, {l,r});
}

int main() {
    cin >> n;
    rep(i,n){
        cin>>p[i];
        if(i&1)odd.update(i,P(p[i],i));
        else even.update(i,P(p[i],i));
    }

    vector<int> ans;
    priority_queue<T,vector<T>,greater<T>>que;
    que.push(calc(0,n));

    while(!que.empty()) {
        P a, b, c;
        tie(a,b,c) = que.top();
        que.pop();

        ans.push_back(a.first);
        ans.push_back(a.second);

        int l,r,ll,rr;
        tie(l,r) = c;
        tie(ll,rr) = b;

        if (l!=ll) que.push(calc(l,ll));
        if (ll + 1 != rr) que.push(calc(ll+1,rr));
        if (rr+1!=r) que.push(calc(rr+1,r));
    }

    rep(i,ans.size()){
        if(i)cout<<" ";
        cout<<ans[i];
    }cout<<endl;
    return 0;
}