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:
// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
	int X=0,w=1; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
	return X*w;
}

const int N=200000+10;

int n,a[N];
struct node { int l,r,p; };
bool operator <(node x,node y) { return a[x.p]>a[y.p]; }
priority_queue<node> Q;

#define ls (o<<1)
#define rs (o<<1|1)
struct SGT {
	int minv[N<<2],type;
	int cmp(int x,int y) { return a[x]<a[y]?x:y; }
	void pushup(int o) { minv[o]=cmp(minv[ls],minv[rs]); }
	void build(int o,int l,int r) {
		if (l==r) { minv[o]=(l&1)==type?l:0; return; }
		int mid=(l+r)>>1;
		build(ls,l,mid),build(rs,mid+1,r);
		pushup(o);
	}
	int query(int o,int l,int r,int ql,int qr) {
		if (ql<=l&&r<=qr) return minv[o];
		int mid=(l+r)>>1,res=0;
		if (ql<=mid) res=cmp(res,query(ls,l,mid,ql,qr));
		if (qr>mid) res=cmp(res,query(rs,mid+1,r,ql,qr));
		return res;
	}
} t[2];
#undef ls
#undef rs

int main() {
	n=read();
	for (int i=1;i<=n;++i) a[i]=read();
	a[0]=1e9;
	t[0].type=0,t[0].build(1,1,n);
	t[1].type=1,t[1].build(1,1,n);
	Q.push((node){1,n,t[1].query(1,1,n,1,n)});
	for (int i=1;i<=(n>>1);++i) {
		int l=Q.top().l,r=Q.top().r,lx=Q.top().p; Q.pop();
		int rx=t[(lx&1)^1].query(1,1,n,lx,r);
		printf("%d %d ",a[lx],a[rx]);
		if (l<lx) Q.push((node){l,lx-1,t[l&1].query(1,1,n,l,lx-1)});
		if (lx<rx) Q.push((node){lx+1,rx-1,t[(lx&1)^1].query(1,1,n,lx+1,rx-1)});
		if (rx<r) Q.push((node){rx+1,r,t[(rx&1)^1].query(1,1,n,rx+1,r)});
	}
	puts("");
	return 0;
}