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
#include<bits/stdc++.h>
#define N 200005
using namespace std;
int lg[N];
int val[20][N];
int p[N];
int n;

int query(int l,int r){
	if(l&1^1) l=l/2,r=r/2;
	else l=n/2+l/2,r=n/2+(r-1)/2;
	int d=lg[r-l+1];
	return p[val[d][r]] < p[val[d][l+(1<<d)-1]] ? val[d][r]:val[d][l+(1<<d)-1];
}

struct msg{
	int l,r,x,y;
	bool operator <(const msg &b)const{
		return p[x]==p[b.x]? p[y] > p[b.y] : p[x] > p[b.x] ;
	}
};
priority_queue<msg> pq;
void add(int l,int r){
	int x=query(l,r);
	int y=query(x+1,r);
	pq.push((msg){l,r,x,y});
}
int main(){
	scanf("%d",&n);
	memset(val,0x3f,sizeof val);
	for(int i=0,t;i<n;i++) scanf("%d",&p[i]);
	
	for(int i=0;i<n;i++)
		val[0][i/2+(n/2)*(i%2)]=i,lg[i]=i<2? 0:lg[i>>1]+1;
	for(int i=1;i<20;i++)
		for(int j=(1<<i)-1,hf=(1<<(i-1));j<n;j++)
			val[i][j]=p[val[i-1][j]] < p[val[i-1][j-hf]] ? val[i-1][j]:val[i-1][j-hf];
	
	add(0,n-1);
	while(!pq.empty()){
		msg v=pq.top();pq.pop();
		printf("%d %d ",p[v.x],p[v.y]);
		if(v.l<v.x) add(v.l,v.x-1);
		if(v.x+1<v.y) add(v.x+1,v.y-1);
		if(v.y<v.r) add(v.y+1,v.r); 
	}
	return 0;
} 