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>
using namespace std;
const int ran = 111111;
int n,_p[ran*2];
int _e[ran],_o[ran];
struct Node{
	int val,pos;
};
Node merge(Node x,Node y){
	return x.val < y.val? x : y;
}
struct segTree{
	Node a[111111*4];
	void build(int i,int l,int r,int*p){
		if(l==r){
			a[i].val = p[l];
			a[i].pos = l;
			return;
		}
		int m=(l+r)/2;
		build(i*2,l,m,p);
		build(i*2+1,m+1,r,p);
		a[i] = merge(a[i*2],a[i*2+1]);
	}
	Node query(int i,int l,int r,int s,int e){
		if(l==s && r==e)
			return a[i];
		int m=(l+r)/2;
		if(e <= m)return query(i*2,l,m,s,e);
		if(s > m)return query(i*2+1,m+1,r,s,e);
		return merge(query(i*2,l,m,s,m),query(i*2+1,m+1,r,m+1,e));
	}
	void build(int*p){build(1,1,n,p);}
} o,e;
struct seg{
	int l,r;
	Node L,R;
	seg(int _l,int _r){
		l = _l; r = _r;
		if(l%2==1){
			L = o.query(1,1,n,(l+1)/2,r/2);
			R = e.query(1,1,n,L.pos,r/2);
		}else{
			L = e.query(1,1,n,l/2,r/2);
			R = o.query(1,1,n,L.pos+1,(r+1)/2);
		}
	}
};
bool operator <(seg A,seg B){
	return A.L.val > B.L.val;
}
priority_queue<seg> q;
int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		scanf("%d",&_p[i]);
	n /= 2;
	for(int i=1; i<=n; i++){
		_o[i] = _p[i*2-1];
		_e[i] = _p[i*2];
	}
	o.build(_o);
	e.build(_e);
	q.push(seg(1,2*n));
	bool fir = false;
	while(!q.empty()){
		seg tmp = q.top();
		q.pop();
		if(fir)printf(" ");
		fir = true;
		printf("%d %d",tmp.L.val, tmp.R.val);
		int l = tmp.l;
		int r = tmp.r;
		int l2 = tmp.L.pos * 2 - l%2;
		int r2 = tmp.R.pos * 2 - (l+1)%2;
		if(l < l2 - 1)q.push(seg(l,l2-1));
		if(l2+1 < r2-1)q.push(seg(l2+1,r2-1));
		if(r2+1 < r)q.push(seg(r2+1,r));
	}
	puts("");
	return 0;
}