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;
const int N=200010;
int n,a[N],sgt[2][N<<2];
inline void add(int op,int pos,int l, int r, int cnt) {
    if(a[cnt]<a[sgt[op][pos]])sgt[op][pos]=cnt;
    if(l==r)return;
	int mid=(l+r)>>1;
	if(cnt<=mid)add(op,pos<<1,l,mid,cnt);
	else add(op,pos<<1|1,mid+1,r,cnt);
}
inline int ask(int op,int pos,int l, int r, int L, int R) {
    if(l>R||r<L)return 0;
    if(L<=l&&r<=R)return sgt[op][pos];
    int mid=(l+r)>>1;
    int lans=ask(op,pos<<1,l,mid,L,R);
	int rans=ask(op,pos<<1|1,mid+1,r,L,R);
	return a[lans]<a[rans]?lans:rans;
}
struct stru{
    int l,r,v;
    stru(int _l,int _r){
    	l=_l,r=_r,v=(l>r)?0:ask(l&1,1,1,n,l,r); 
	}
	bool operator <(const stru &other) const{
		return a[v]<a[other.v]; 
	}
};
set<stru> s;
int main(){
	scanf("%d",&n);a[0]=n+1;
    for(int i=1;i<=n;i++){
    	scanf("%d",&a[i]);
        add(i&1,1,1,n,i);
    }
    s.insert(stru(1,n));
    for(int i=1;i<=n>>1;i++){
        stru now=*s.begin();
        s.erase(s.begin());
        int l=now.l,r=now.r;
        int lmid=now.v,rmid=ask((lmid&1)^1,1,1,n,lmid,r);
        printf("%d %d ",a[lmid],a[rmid]);
        s.insert(stru(l,lmid-1));
        s.insert(stru(lmid+1,rmid-1));
        s.insert(stru(rmid+1,r));
    }
    return 0;
}