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 <iostream>
#include <queue>
using namespace std;

const int SIZE=(1<<20);
int p[200010], ans[200010], loc[200010];

struct RMQ{
	int data[SIZE*2];
	void update(int n, int x){
		n += SIZE-1;
		data[n]=x;
		while(n>0){
			n=(n-1)/2;
			data[n]=min(data[n*2+1], data[n*2+2]);
		}
	}
	int query(int a, int b, int k, int l, int r){
		if(b<=l || r<=a) return 1e9;
		if(a<=l && r<=b) return data[k];
		else return min(query(a, b, k*2+1, l, (l+r)/2), query(a, b, k*2+2, (l+r)/2, r));
	}
};

RMQ even, odd;

struct section{
	int L, R, mn;
	section(int inputtedL, int inputtedR){
		L=inputtedL, R=inputtedR;
		if(L%2==0) mn=even.query(L/2, R/2, 0, 0, SIZE);
		else mn=odd.query(L/2, R/2, 0, 0, SIZE);
	}
	bool operator<(const section a) const{
		return mn < a.mn;
	}
	bool operator>(const section a) const{
		return mn > a.mn;
	}
};

priority_queue<section, vector<section>, greater<section>> pq;

int main() {
	int N;
	cin >> N;
	for(int i=0; i<N; ++i){
		cin >> p[i];
		loc[p[i]]=i;
	}
	for(int i=0; i*2<N; ++i){
		even.update(i, p[i*2]);
		odd.update(i, p[i*2+1]);
	}
	pq.push(section(0, N));
	for(int i=0; i*2<N; ++i){
		int ss=pq.top().mn, lt=pq.top().L, rt=pq.top().R;
		pq.pop();
		if(lt<loc[ss]){
			pq.push(section(lt, loc[ss]));
		}
		int tt;
		if(loc[ss]%2==0) tt=odd.query(loc[ss]/2, rt/2, 0, 0, SIZE);
		else tt=even.query(loc[ss]/2+1, rt/2+1, 0, 0, SIZE);
		if(loc[ss]+1<loc[tt]){
			pq.push(section(loc[ss]+1, loc[tt]));
		}
		if(loc[tt]<rt){
			pq.push(section(loc[tt]+1, rt));
		}
		ans[i*2]=ss, ans[i*2+1]=tt;
	}
	cout << ans[0];
	for(int i=1; i<N; ++i) cout << ' ' << ans[i];
	cout << endl;
	return 0;
}