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,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
#define MOD 1000000007

using namespace std;
typedef long long int ll;
typedef pair <int,int> P_;
typedef pair <int,P_> P;

struct tree{
	int idx;
	int v;
};

bool comp(const tree &a,const tree &b){
	return a.v < b.v;
}

int N;
int n;
tree dat[2][1<<19];

//配列、木:0オリジン
//n_:元の数列の要素数
//n:修正後の配列要素数 木のサイズ:2*n-1
void init(int n_){
	n=1;
	while(n<n_)n*=2;
	for(int i=0;i<2*n-1;i++) rep(j,0,2){
		dat[j][i].v=INF;
		dat[j][i].idx=i-n+1;
	}
}

void update(int i,int x){
	int u = i%2;
	i += n-1;
	dat[u][i].v = x;
	while(i>0){
		i = (i-1)/2;
		dat[u][i] = min(dat[u][i*2+1],dat[u][i*2+2],comp);
	}
}

//[a,b)のmin 節点k[l,r)について調べる
tree find(int u,int a,int b,int k=0,int l=0,int r=n){
	if(r<=a || b<=l){
		return (tree){INF,INF};
	}else if(a<=l && r<=b){
		return dat[u][k];
	}else{
		tree t1 = find(u,a,b,2*k+1,l,(l+r)/2);
		tree t2 = find(u,a,b,2*k+2,(l+r)/2,r);
		return min(t1,t2,comp);
	}
}

priority_queue<P,vector<P>,greater<P>> que;

//[l,r)
void push(int l,int r){
	if(r-l<2)return;
	que.push(P(find(l%2,l,r).v,P_(l,r)));
}

int main()
{
	cin >> N;
	init(N+1);
	rep(i,0,N){
		int p;
		cin >> p;
		update(i,p);
	}
	push(0,N);
	vector<int> ans;

	while(!que.empty()){
		P R = que.top();que.pop();
		int l = R.second.first;
		int r = R.second.second;
		tree t1 = find(l%2,l,r);
		tree t2 = find((l+1)%2,t1.idx,r);
		ans.push_back(t1.v);
		ans.push_back(t2.v);
		push(l,t1.idx);
		push(t1.idx+1,t2.idx);
		push(t2.idx+1,r);
	}
	rep(i,0,ans.size()){
		if(i!=0)cout << " ";
		cout << ans[i];
	}
	cout << endl;

	return 0;
}