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;
typedef long long ll;
typedef pair<int,int> PI;
const int MAX_N=2e5+10;
PI seg0[2][MAX_N*4];
void modify(int l,int r,int pos,int v,int idx,PI* seg){
	if(l==r){
		seg[idx]=PI(v,l);
	}else{
		int mid=(l+r)>>1;
		if(pos<=mid)
			modify(l,mid,pos,v,idx<<1,seg);
		else
			modify(mid+1,r,pos,v,idx<<1|1,seg);
		seg[idx]=min(seg[idx<<1],seg[idx<<1|1]);
	}
}
PI query(int l,int r,int ql,int qr,int idx,PI* seg){
	if(l==ql && r==qr){
		return seg[idx];
	}
	int mid=(l+r)>>1;
	if(qr<=mid)
		return query(l,mid,ql,qr,idx<<1,seg);
	else if(ql>mid)
		return query(mid+1,r,ql,qr,idx<<1|1,seg);
	else{
		return min(query(l,mid,ql,mid,idx<<1,seg),query(mid+1,r,mid+1,qr,idx<<1|1,seg));
	}
}
struct Status{
	int l,r,v,pos;
	bool operator<(const Status& rhs) const{
		return v>rhs.v;
	}
};
int a[MAX_N],ans[MAX_N];
priority_queue<Status> pq;
int main(){
	memset(seg0,0x3f,sizeof seg0);
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",a+i);
		modify(0,n-1,i,a[i],1,seg0[i&1]);
	}
	PI res=query(0,n-1,0,n-1,1,seg0[0]);
	pq.push((Status){0,n-1,res.first,res.second});
	int p=0;
	while(!pq.empty()){
		Status now=pq.top();
		pq.pop();
		res=query(0,n-1,now.pos+1,now.r,1,seg0[(now.l+1)&1]);
		int l=now.pos,r=res.second;
		ans[p++]=a[l];
		ans[p++]=a[r];
		int ql=l+1,qr=r-1;
		if(ql<qr){
			res=query(0,n-1,ql,qr,1,seg0[ql&1]);
			pq.push((Status){ql,qr,res.first,res.second});
		}
		ql=now.l,qr=l-1;
		if(ql<qr){
			res=query(0,n-1,ql,qr,1,seg0[ql&1]);
			pq.push((Status){ql,qr,res.first,res.second});
		}
		ql=r+1,qr=now.r;
		if(ql<qr){
			res=query(0,n-1,ql,qr,1,seg0[ql&1]);
			pq.push((Status){ql,qr,res.first,res.second});
		}
	}
	for(int i=0;i<n;i++)
		printf("%d%c",ans[i],i==n-1?'\n':' ');
	return 0;
}