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 <string>
#include<queue>
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<map>
#include<tuple>

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> t3;
typedef tuple<int,int,int,int> t4;

const int MX = 1<<18;

struct Tree{
	pii t[MX*2];
	pii find(int s, int e){
		s += MX, e += MX;
		pii r = pii(1e9, -1);
		while(s <= e){
			if( s&1 ) r = min(r, t[s++]);
			if(~e&1 ) r = min(r, t[e--]);
			s /= 2, e /= 2;
		}
		return r;
	}
	void update(int x, int v){
		x += MX; t[x] = pii(v, x-MX);
		while(x > 1) x /= 2, t[x] = min(t[x*2], t[x*2+1]);
	}
} t[2];

int D[MX];

int main()
{
	int N, s = 1;
	scanf("%d", &N);
	for(int i = 1; i <= N; i++) t[0].update(i, 1e9), t[1].update(i, 1e9);
	for(int i = 1; i <= N; i++){
		scanf("%d", D+i);
		t[i%2].update(i, D[i]);
	}
	set<t4> X;
	pii p = t[1].find(1, N);
	X.insert(t4(p.first, p.second, 1, N));
	for(int i = 1; i*2 <= N; i++){
		int a, b, c, d; tie(a, b, c, d) = *X.begin();
		X.erase(X.begin());
		printf("%d ", a);
		pii p = t[~b&1].find(b+1, d);
		printf("%d ", p.first);
		auto ins = [&](int s, int e){
			if( s > e ) return;
			pii p = t[s&1].find(s, e);
			X.insert(t4(p.first, p.second, s, e));
		};
		ins(c, b-1);
		ins(b+1, p.second-1);
		ins(p.second+1, d);
	}
}