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 <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m[530000][2],li,id[200001],tot;
struct Node{
	int l,r,x,b,e;
};
bool operator < (Node x,Node y){
	return m[x.l+li][x.x]>m[y.l+li][y.x];
}
priority_queue <Node> q;
void build(){
	for (int i=li-1;i;--i){
		m[i][0]=m[i<<1][0]<m[i<<1|1][0]?m[i<<1][0]:m[i<<1|1][0];
		m[i][1]=m[i<<1][1]<m[i<<1|1][1]?m[i<<1][1]:m[i<<1|1][1];
	}
}
int query(int l,int r,int x){
	int ans=inf;
	for (l+=li-1,r+=li+1;l^r^1;l>>=1,r>>=1){
		if (~l&1&&ans>m[l^1][x]) ans=m[l^1][x];
		if (r&1&&ans>m[r^1][x]) ans=m[r^1][x];
	}
	return ans;
}
Node make(int b,int e,int x){
	int t=id[query(b,e,x)];
	return (Node){t,id[query(t,e,x^1)],x,b,e};
}
void read(int& x){
    x=0;
    int y=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') y=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    x=x*y;
}
int main(){
	int i,x;
	Node y;
	read(n);
	memset(m,0x3f,sizeof(m));
	for (li=1;li<n+2;li<<=1);
	for (i=1;i<=n;++i){
		read(m[i+li][i&1]);
		id[m[i+li][i&1]]=i;
	}
	build();
	q.push(make(1,n,1));
	n>>=1;
	for (i=1;i<=n;++i){
		y=q.top();
		q.pop();
		printf("%d %d ",m[li+y.l][y.x],m[li+y.r][y.x^1]);
		if (y.b<y.l) q.push(make(y.b,y.l-1,y.x));
		if (y.r<y.e) q.push(make(y.r+1,y.e,y.x));
		if (y.l+1<y.r) q.push(make(y.l+1,y.r-1,y.x^1));
	}
	return 0;
}