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 <cstdio>
#include <algorithm>
#include <set>
using namespace std;

const int MAXN = 200005;
const int offset = 1 << 18;

struct node {
	int mn, pos;
};

int N;
int p[MAXN];
int a[2][MAXN];

struct segment {
	int lo, hi, pos;
	bool operator <(const segment &rhs) const {
		return p[pos] < p[rhs.pos];
	}
};

set <segment> S;

struct tournament {
	node t[2 * offset];	
	node merge(node l, node r) {
		return {min(l.mn, r.mn), l.mn < r.mn ? l.pos : r.pos};
	}
	void init(int *arr) {
		for (int i = 0; i < N; i++)
			t[i + offset] = {arr[i], i};
		for (int i = offset - 1; i >= 0; i--)
			t[i] = merge(t[2 * i], t[2 * i + 1]);
	}
	node query(int x, int lo, int hi, int from, int to) {
		if (lo >= to || hi <= from)
			return {N + 1, 0};
		if (lo >= from && hi <= to)
			return t[x];
		int mid = (lo + hi) / 2;
		return merge(query(2 * x, lo, mid, from, to), query(2 * x + 1, mid, hi, from, to));
	}
	int query(int from, int to) {
		return query(1, 0, offset, from, to).pos;
	}
};

tournament T[2];

void load() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d", p + i);
}

int get(int l, int r, int parity) {
	return T[(l + parity) % 2].query(l, r);
}

void add(int l, int r) {	
	if (l < r)
		S.insert({l, r, get(l, r, 0)});
}

void solve() {
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < N; j++)
			a[i][j] = j % 2 == i ? p[j] : N + 1;
		T[i].init(a[i]);
	}
	
	add(0, N);
	for (int i = 0; i < N / 2; i++) {
		segment tmp = *S.begin();
		S.erase(tmp);
		int curr = get(tmp.pos, tmp.hi, 1);
		printf("%d %d ", p[tmp.pos], p[curr]);
		add(tmp.lo, tmp.pos);
		add(tmp.pos + 1, curr);
		add(curr + 1, tmp.hi);
	}
	puts("");
}

int main() {
	load();
	solve();
	return 0;
}