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 <queue>

const int INF = 0x1f1f1f1f;

const int N = 200100;

const int lgN = 20;

typedef int ST[lgN][N];

ST st[2];

int p[N];

int lg[N];

int inv[N];

int qi;
int q[N];

int n;

void build(int d) {
	for (int x = 0; (1 << x) <= n; x++) {
		int y = 1 << x;
		int h = y >> 1;
		for (int i = 0; i <= n - y; i++) {
			if (x == 0)
				st[d][x][i] = i % 2 == d ? p[i] : INF;
			else
				st[d][x][i] = std::min(st[d][x - 1][i], st[d][x - 1][i + h]);
		}
	}
}

int query(int l, int r) {
	int x = lg[r - l + 1];
	return std::min(st[l % 2][x][l], st[l % 2][x][r - (1 << x) + 1]);
}

void init() {
	for (int i = 0; (1 << i) + 1 <= n; i++)
		lg[1 << i] = i;
	for (int i = 2; i <= n; i++)
		lg[i] = lg[i] == 0 ? lg[i - 1] : lg[i];
}

struct pair {
	int l, r, val;
	friend bool operator < (const pair& a, const pair& b) {
		return a.val > b.val;
	}
};

pair make_pair(int l, int r) {
	return (pair){l, r, query(l, r)};
}

std::priority_queue<pair> pq;

void solve() {

	pq.push(make_pair(0, n - 1));

	while (!pq.empty()) {

		pair t = pq.top();
		pq.pop();

		q[qi++] = t.val;

		int i = inv[t.val];

		int j_ = query(i + 1, t.r);

		q[qi++] = j_;

		int j = inv[j_];

		if (t.l < i - 1) pq.push(make_pair(t.l, i - 1));
		if (i + 1 < j - 1) pq.push(make_pair(i + 1, j - 1));
		if (j + 1 < t.r) pq.push(make_pair(j + 1, t.r));

	}

}

int main(int argc, char *argv[]) {
	
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &p[i]);
		inv[p[i]] = i;
	}
		
	init();
	
	build(0);
	build(1);
	
	solve();
	
	for (int i = 0; i < qi; i++)
		printf("%d ", q[i]);
	putchar('\n');
	
	return 0;

}