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 pb push_back
#define ll long long
#define int long long
#define mp make_pair
#define inf 1000000007
using namespace std;
typedef pair<int,pair<int,int> > P;
int N;
ll seg[2][530000]; // 0:even, 1:odd range minimum
void init(int n_){
	N = 1;
	while(N<n_)N*=2;
	for(int i=0;i<2*N-1;i++){
		seg[0][i]=inf;
		seg[1][i]=inf;
	}
}

void update(int k,int a,int x){
	k += N-1;
	seg[x][k]=a;
	while(k>0){
		k = (k-1)/2;
		seg[x][k] = min(seg[x][k*2+1],seg[x][k*2+2]);
	}
}

ll query(int a,int b, int k, int l, int r,int x){ 
	if(r<=a || b<=l) return inf;
	if(a<=l && r<=b) return seg[x][k];
	else{
		ll vl = query(a,b,k*2+1,l,(l+r)/2,x);
		ll vr = query(a,b,k*2+2,(l+r)/2,r,x);
		return min(vl,vr);
	}
}
int inv[214514];
signed main(){
	int n;
	cin>>n;
	init(n);
	vector<int> ans;
	for(int i=0;i<n;i++){
		int tmp;
		cin>>tmp;
		update( i, tmp, i%2 );
		inv[tmp] = i;
	}
	priority_queue< P > que;
	que.push( mp( -query(0,n,0,0,N,0), mp(0,n-1) ) );
	while( !que.empty() ){
		P cur = que.top();que.pop();
		int lf = cur.second.first;
		int rg = cur.second.second;
		int mi = -cur.first;
		ans.pb(mi);
		int imi = inv[mi];
		int mi2 = query(imi+1,rg+1,0,0,N,(imi+1)%2);
		ans.pb(mi2);
		int imi2 = inv[mi2];
		if( imi-1 > lf){
			que.push( mp( -query(lf,imi,0,0,N,lf%2), mp(lf,imi-1) ) );
		}
		if( imi2-1 > imi+1){
			que.push( mp( -query(imi+1,imi2,0,0,N,(imi+1)%2), mp(imi+1,imi2-1) ) );
		}
		if( rg > imi2+1){
			que.push( mp( -query(imi2+1,rg+1,0,0,N,(imi2+1)%2), mp(imi2+1,rg) ) );
		}
	}
	for(int i=0;i<ans.size();i++){
		cout<<ans[i]<<" ";
	}
	cout<<endl;
	return 0;
}