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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for (int i = x; i < (int)(n); ++i)

int n, x[200000];
bool out;

struct S{
	pair<int, int> a, b;
	S(){}
	S(int x, int y, int z, int w):a(x, y), b(z, w) {}
	S operator +(S o){
		S an;
		an.a = min(a, o.a);
		an.b = min(b, o.b);
		return an;
	}
}s[800000];

void bld(int l = 0, int r = n, int id = 1){
	if (l + 1 == r) { s[id] = S(1e6, l, 1e6, l); if (l & 1)s[id].b.first = x[l]; else s[id].a.first = x[l]; return; }
	int m = l + r >> 1, a = id << 1, b = a | 1;
	bld(l, m, a);
	bld(m, r, b);
	s[id] = s[a] + s[b];
}

S gt(int x, int y, int l = 0, int r = n, int id = 1){
	if (l >= y || r <= x)return S(1e6, 1e6, 1e6, 1e6);
	if (l >= x && r <= y)return s[id];
	int m = l + r >> 1, a = id << 1, b = a | 1;
	return gt(x, y, l, m, a) + gt(x, y, m, r, b);
}

S gtint(int l, int r){
	S an, t = gt(l, r);
	if (l & 1)an.a = t.b; else an.a = t.a;
	t = gt(an.a.second, r);
	if (l & 1)an.b = t.a; else an.b = t.b;
	return an;
}

void go(){
	priority_queue<pair<int, pair<int, int> > > q;
	q.push(make_pair(0, make_pair(0, n)));
	while (!q.empty()){
		int l = q.top().second.first, r = q.top().second.second;
		q.pop();
		S z = gtint(l, r);
		if (out)printf(" ");
		out = true;
		printf("%d %d", z.a.first, z.b.first);
		if (l !=  z.a.second)q.push(make_pair(-gtint(l, z.a.second).a.first, make_pair(l, z.a.second)));
		if (z.a.second + 1 != z.b.second)q.push(make_pair(-gtint(z.a.second + 1, z.b.second).a.first, make_pair(z.a.second + 1, z.b.second)));
		if (z.b.second + 1 != r)q.push(make_pair(-gtint(z.b.second + 1, r).a.first, make_pair(z.b.second + 1, r)));
	}
}

int main(){
	scanf("%d", &n);
	f(i, 0, n)scanf("%d", x + i);
	bld();
	go();
	printf("\n");
}