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;
#define N 200005
#define L first
#define R second
#define mk make_pair
#define pa pair<int,int>
int a[N],lg[N];
pa v[2][20][N];
priority_queue<pair<int,pa > > q;
int n;
int rmq(int tp,int l,int r){
	int k=lg[r-l+1];
	return min(v[tp][k][l],v[tp][k][r-(1<<k)+1]).R;
}
void push(int l,int r){
	if (r<l) return;
	q.push(mk(-a[rmq((l&1)^1,l,r)],pa(l,r)));
}
int main(){
	scanf("%d",&n);
	a[0]=1e9;
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for (int i=2;i<=n;i++)
		lg[i]=lg[i>>1]+1;
	for (int i=1;i<=n;i++)
		v[0][0][i]=pa((i&1)?a[i]:1e9,i);
		
	for (int i=1;i<=n;i++)
		v[1][0][i]=pa((i&1)?1e9:a[i],i);
	for (int j=1;j<=17;j++)
		for (int k=1;k+(1<<j)-1<=n;k++){
			v[0][j][k]=min(v[0][j-1][k],v[0][j-1][k+(1<<(j-1))]);
			v[1][j][k]=min(v[1][j-1][k],v[1][j-1][k+(1<<(j-1))]);
		}
	push(1,n);
	while (!q.empty()){
		pa x=q.top().R; q.pop();
		int md1=rmq((x.L&1)^1,x.L,x.R);
		int md2=rmq((x.L&1)^0,md1,x.R);
		push(x.L,md1-1);
		push(md1+1,md2-1);
		push(md2+1,x.R);
		printf("%d %d ",a[md1],a[md2]);
	}
}