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>
#ifdef DEMETRIO
#define deb(...) fprintf(stderr,__VA_ARGS__)
#define deb1(x) cerr << #x << " = " << x << endl
#else
#define deb(...) 0
#define deb1(x) 0
#endif
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define SZ(x) ((int)x.size())
using namespace std;
typedef long long ll;

#define INF (1<<30)

#define oper min
#define NEUT mp(INF,INF)
#define K 18

struct ST {
	pair<int,int> st[K][1<<K];int n;  // K such that 2^K>n
	void init(pair<int,int> *a, int _n){
		n=_n;
		fore(i,0,n)st[0][i]=a[i];
		fore(k,1,K)fore(i,0,n-(1<<k)+1)
			st[k][i]=oper(st[k-1][i],st[k-1][i+(1<<(k-1))]);
	}
	pair<int,int> query(int s, int e){
		int k=31-__builtin_clz(e-s);
		return oper(st[k][s],st[k][e-(1<<k)]);
	}
};

int n;
pair<int,int> v[2][200005];
ST w[2];

priority_queue<pair<int,pair<int,int> > > qq;
vector<int> r;

int main(){
	scanf("%d",&n);
	fore(i,0,n){
		int x;
		scanf("%d",&x);
		v[i%2][i]=mp(x,i);v[1-i%2][i]=NEUT;
	}
	w[0].init(v[0],n);w[1].init(v[1],n);
	qq.push(mp(-w[0].query(0,n).fst,mp(0,n)));
	while(!qq.empty()){
		auto _=qq.top();qq.pop();
		int s=_.snd.fst,e=_.snd.snd;
		auto p=w[s%2].query(s,e);r.pb(p.fst);
		auto q=w[1-s%2].query(p.snd+1,e);r.pb(q.fst);
		if(s<p.snd)qq.push(mp(-w[s%2].query(s,p.snd).fst,mp(s,p.snd)));
		if(p.snd+1<q.snd)qq.push(mp(-w[(p.snd+1)%2].query(p.snd+1,q.snd).fst,mp(p.snd+1,q.snd)));
		if(q.snd+1<e)qq.push(mp(-w[(q.snd+1)%2].query(q.snd+1,e).fst,mp(q.snd+1,e)));
	}
	assert(r.size()==n);
	fore(i,0,r.size()){
		if(i)putchar(' ');
		printf("%d",r[i]);
	}
	puts("");
	return 0;
}