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 <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>

using namespace std;

const int MAXN = 200000 + 1000;
const int MAXK = 20;


int n, p[MAXN];
pair<int, int> rmq[MAXN][MAXK];
vector<int> ans;

pair<int, int> query(int l, int r)
{
	if((r - l + 1) & 1) r++;
	// cerr << l << ' '<< r << endl;
	int k = log2(r - l + 1);
	// cerr << k << endl;
	return min(rmq[l][k], rmq[r - (1 << k) + 1][k]);
}

struct State
{
	pair<int, int> v;
	int l, r;
	State(int _l = 0, int _r = 0) : v(query(_l, _r)), l(_l), r(_r)
	{}
	bool operator < (const State &s) const
	{
		return v > s.v;
	}
};
priority_queue<State> pq;

int main()
{
	ios::sync_with_stdio(false);
	// freopen("1.in", "r", stdin);
	// freopen("1.out", "w", stdout);

	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> p[i];
	for(int i = 0; i < n; i++)
		rmq[i][0] = rmq[i][1] = make_pair(p[i], i);
	for(int j = 2; j < MAXK; j++)
		for(int i = 0; i + (1 << (j - 1)) < n; i++)
			rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);

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

	while(!pq.empty())
	{
		State s = pq.top();
		pq.pop();
		int p0 = s.v.second, l = s.l, r = s.r;
		int p1 = query(p0 + 1, r).second;
		ans.push_back(p[p0]);
		ans.push_back(p[p1]);
		if(l <= p0 - 1) pq.push(State(l, p0 - 1));
		if(p0 + 1 <= p1 - 1) pq.push(State(p0 + 1, p1 - 1));
		if(p1 + 1 <= r)	pq.push(State(p1 + 1, r));
	}
	for(int i = 0; i < n; i++)
		cout << ans[i] << ' ';
	cout << endl;

	return 0;
}
