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>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define mset(x, y) memset(x, y, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

inline int Read()
{
	int x = 0, f = 1, c = getchar();
	for (; !isdigit(c); c = getchar())
		if (c == '-')
			f = -1;
	for (;  isdigit(c); c = getchar())
		x = x * 10 + c - '0';
	return x * f;
}

const int MAXN = 200005;

int n, a[MAXN], lg[MAXN];
pii f[2][18][MAXN];

struct Node
{
	int l, r, k;
	bool operator < (const Node &b) const { return a[k] > a[b.k]; }
};

priority_queue <Node> q;

inline int Query(int l, int r, bool t)
{
	t ^= l & 1;
	int k = lg[r - l + 1];
	return min(f[t][k][l], f[t][k][r - (1 << k) + 1]).yy;
}

inline void Insert(int l, int r)
{
	if (l < r)
		q.push({l, r, Query(l, r, 0)});
}

int main()
{
#ifdef wxh010910
	freopen("data.in", "r", stdin);
#endif
	n = Read();
	for (int i = 1; i <= n; i ++)
		a[i] = Read(), f[i & 1][0][i] = mp(a[i], i), f[i & 1 ^ 1][0][i] = mp(n + 1, i);
	for (int i = 2; i <= n; i ++)
		lg[i] = lg[i >> 1] + 1;
	for (int k = 0; k < 2; k ++)
		for (int i = 1; i < 18; i ++)
			for (int j = 1; j + (1 << i) - 1 <= n; j ++)
				f[k][i][j] = min(f[k][i - 1][j], f[k][i - 1][j + (1 << i - 1)]);
	for (Insert(1, n); !q.empty(); )
	{
		Node t = q.top(); q.pop();
		int l = t.l, r = t.r, x = t.k, y = Query(x, t.r, 1);
		printf("%d %d ", a[x], a[y]);
		Insert(l, x - 1), Insert(x + 1, y - 1), Insert(y + 1, r);
	}
	return 0;
}