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 1111116

int n,a[N],f[N][18];

struct rec{int l,r,x,y;};
priority_queue<rec> q;

bool operator <(rec x,rec y){
	return a[x.x]>a[y.x];
}

int mn(int x,int y){
	return a[x]<a[y]?x:y;
}

int query(int l,int r){
	int t=0;while (1<<(t+1)<=r-l+1) t++;
	return mn(f[l][t],f[r-(1<<t)+1][t]);
}

void push(int l,int r){
	if (l>r) return;
	int x=query(l,r),y=x+1==r?r:mn(query(x+1,r-1),r);
	q.push((rec){l,r,x,y});
}

int read(){
	int x=0,f=1;char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-')  f=-f;
	for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x*f;
}

int main(){
	n=read();
	for (int i=1;i<=n;i++) a[i]=read(),f[i][0]=f[i][1]=i;
	for (int k=2;(1<<k)<=n;k++)
		for (int i=1;i<=n-(1<<k)+1;i++)
			f[i][k]=mn(f[i][k-1],f[i+(1<<(k-1))][k-1]);
	for (push(1,n);!q.empty();){
		rec t=q.top();q.pop();
		printf("%d %d ",a[t.x],a[t.y]);
		push(t.l,t.x-1);
		push(t.x+1,t.y-1);
		push(t.y+1,t.r);
	}
	printf("\n");return 0;
}