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;
typedef long long ll;
typedef pair<int, int>P;
#define MAX 800000

int p[400000], q[400000];

template<class T,class comp>
class SegTree{
public:
	int n;
	T dat[MAX],def;
	void init(int n_,T d){
		def=d;
		n=1;while(n<n_)n*=2;
		for(int i=0;i<2*n-1;i++)dat[i]=def;
	}
	void update(int k,T a){
		k+=n-1;dat[k]=a;
		while(k){
			k=(k-1)/2;
			dat[k]=min(dat[k*2+1],dat[k*2+2]);
		}
	}
	T query(int a,int b,int k,int l,int r){
		if(a>=b||r<=a||b<=l)return def;
		if(a<=l&&r<=b)return dat[k];
		T vl=query(a,b,k*2+1,l,(l+r)/2);
		T vr=query(a,b,k*2+2,(l+r)/2,r);
		if(comp()(vl,vr))return vl;
		return vr;
	}
	T query(int a,int b){
		return query(a,b,0,0,n);
	}
};
SegTree<P,less<P>>t[2];

struct st{
	int l,r;
	bool operator<(const st&b)const{
		return t[l%2].query(l,r)>t[b.l%2].query(b.l,b.r);
	}
};
int main() {
	int n; scanf("%d", &n);
	t[0].init(n,P(INT_MAX,0)); t[1].init(n,P(INT_MAX,0));
	rep(i, n) {
		scanf("%d", &p[i]);
		t[i % 2].update(i, P(p[i], i));
	}
	priority_queue<st>que;
	que.push({0,n});
	int d=0;
	while(!que.empty()){
		st p=que.top();que.pop();
		P a=t[p.l%2].query(p.l,p.r);
		P b=t[!(p.l%2)].query(a.second+1,p.r);
		q[d++]=a.first;q[d++]=b.first;
		if(p.l<a.second)que.push({p.l,a.second});
		if(a.second+1<b.second)que.push({a.second+1,b.second});
		if(b.second+1<p.r)que.push({b.second+1,p.r});
	}
	rep(i, n) {
		if (i)printf(" ");
		printf("%d", q[i]);
	}
	puts("");
}