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<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;

const int N=200005;
const int inf=1000000000;

struct ST{
	int l,r,mn,pos;
}t[2][N<<2];
int n,l,r,m;
int a[N],b[N];
struct node{
	int l,r,x,y;
	node(){}
	node(int l,int r,int x,int y):l(l),r(r),x(x),y(y){}
	friend bool operator<(node c,node d){
		return a[c.x]>a[d.x];
	}
};
priority_queue<node> q;

void update(int k){
	t[0][k].mn=min(t[0][k<<1].mn,t[0][k<<1|1].mn);
	if (t[0][k].mn==t[0][k<<1].mn) t[0][k].pos=t[0][k<<1].pos;
	else t[0][k].pos=t[0][k<<1|1].pos;
	t[1][k].mn=min(t[1][k<<1].mn,t[1][k<<1|1].mn);
	if (t[1][k].mn==t[1][k<<1].mn) t[1][k].pos=t[1][k<<1].pos;
	else t[1][k].pos=t[1][k<<1|1].pos;
}

void build(int k,int l,int r){
	t[0][k].l=l; t[0][k].r=r;
	t[1][k].l=l; t[1][k].r=r;
	if (l==r){
		t[l&1][k].mn=a[l];
		t[l-1&1][k].mn=inf;
		t[0][k].pos=t[1][k].pos=l;
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	update(k);
}

void query(int tp,int k,int L,int R,int &mn,int &p){
	if (L<=t[tp][k].l&&t[tp][k].r<=R){
		if (t[tp][k].mn<mn) mn=t[tp][k].mn,p=t[tp][k].pos;
		return;
	}
	int mid=(t[tp][k].l+t[tp][k].r)>>1;
	if (L<=mid) query(tp,k<<1,L,R,mn,p);
	if (R>mid) query(tp,k<<1|1,L,R,mn,p); 
}

void push(int l,int r){
	int a,b,p1,p2;
	a=b=inf;
	query(l&1,1,l,r,a,p1);
	query(l-1&1,1,p1,r,b,p2);
	q.push(node(l,r,p1,p2));
}

int main(){
	int i; node k;
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d",&a[i]);
	build(1,1,n);
	push(1,n);
	while (!q.empty()){
		k=q.top(); q.pop();
		b[++m]=k.x; b[++m]=k.y;
		if (k.l+1<k.x) push(k.l,k.x-1);
		if (k.y+1<k.r) push(k.y+1,k.r);
		if (k.x+1<k.y) push(k.x+1,k.y-1);
	}
	for (i=1;i<=m;i++) printf("%d ",a[b[i]]);
	return 0;
}