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 N=200010,M=19,oo=1e9;
int n,a[N],maxp,pow2[M];
pair<int,int> st[2][N][M];
struct Node{
	int l,r,v,o;
	bool operator<(Node k)const{return v>k.v;}
	Node(int a=0,int b=0,pair<int,int> c=make_pair(0,0)){
		l=a,r=b,v=c.first,o=c.second;
	}
};
priority_queue<Node>q;
pair<int,int> que(int l,int r,bool b){
	int p=0,len=r-l+1;
	while((1<<p)<len) p++;
	p--;
	b=(l&1)?b:!b;
	pair<int,int> ans=st[b][l][p];
	if(st[b][r-pow2[p]+1][p].first<ans.first) ans=st[b][r-pow2[p]+1][p];
	return ans;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	while((1<<maxp)<n) maxp++;
	pow2[0]=1;
	for(int i=1;i<=maxp;i++) pow2[i]=2*pow2[i-1];
	for(int i=1;i<=n;i++){
		st[i&1][i][0]=make_pair(a[i],i);
		st[(i&1)^1][i][0]=make_pair(oo,i);
	}
	for(int i=0;i<=maxp;i++) st[0][n+1][i]=st[1][n+1][i]=make_pair(oo,n+1);
	for(int i=1;i<=maxp;i++){
		for(int j=1;j<=n;j++){
			if(st[0][j][i-1].first<st[0][min(j+pow2[i-1],n+1)][i-1].first) st[0][j][i].first=st[0][j][i-1].first,st[0][j][i].second=st[0][j][i-1].second;
			else st[0][j][i].first=st[0][min(j+pow2[i-1],n+1)][i-1].first,st[0][j][i].second=st[0][min(j+pow2[i-1],n+1)][i-1].second;
			if(st[1][j][i-1].first<st[1][min(j+pow2[i-1],n+1)][i-1].first) st[1][j][i].first=st[1][j][i-1].first,st[1][j][i].second=st[1][j][i-1].second;
			else st[1][j][i].first=st[1][min(j+pow2[i-1],n+1)][i-1].first,st[1][j][i].second=st[1][min(j+pow2[i-1],n+1)][i-1].second;
		}
	}
	q.push(Node(1,n,que(1,n,1)));
	int o1,o2;
	while(!q.empty()){
		Node x;
		x=q.top();q.pop();
		o1=x.o,o2=que(o1,x.r,0).second;
		printf("%d %d ",a[o1],a[o2]);
		if(o1>x.l) q.push(Node(x.l,o1-1,que(x.l,o1-1,1)));
		if(o1<o2-1) q.push(Node(o1+1,o2-1,que(o1+1,o2-1,1)));
		if(o2<x.r) q.push(Node(o2+1,x.r,que(o2+1,x.r,1)));
	}
	return 0;
}