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 pair<int, int>P;

P p[2][400000];
int q[400000];

#define MAX_LOG 22
template<class T,class comp>
class SparseTable {
	vector<T>t[MAX_LOG];
	vector<int>l2;
public:
	T DEFAULT;
	int n;
	void init(int n_,T DEF) {
		DEFAULT=DEF;
		n = n_;
		rep(i, MAX_LOG)t[i].assign(n, DEFAULT);
		l2.assign(n + 1, 0);
		int k = 0;
		rep(i, n + 1) {
			while ((1 << (k + 1)) <= i)k++;
			l2[i] = k;
		}
	}
	void set_array(int n_, T*a,T DEF) {
		init(n_,DEF);
		rep(i, n)t[0][i] = a[i];
		for (int i = 1; i < MAX_LOG; i++) {
			for (int j = 0; j + (1 << (i - 1)) < n; j++){
				if(comp()(t[i-1][j],t[i-1][j+(1<<(i-1))]))t[i][j]=t[i-1][j];
				else t[i][j]=t[i-1][j+(1<<(i-1))];
			}
		}
	}
	T query(int a, int b) {
		int w = b - a;
		int l = l2[w];
		return comp()(t[l][a],t[l][b-(1<<l)])?t[l][a]:t[l][b - (1 << l)];
	}
};
SparseTable<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);
	rep(i, n) {
		scanf("%d", &p[i%2][i].first);
		p[!(i%2)][i].first=INT_MAX;
		p[i%2][i].second=i;
	}
	t[0].set_array(n,p[0],P(INT_MAX,0));t[1].set_array(n,p[1],P(INT_MAX,0));
	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("");
}