#include <bits/stdc++.h>

using namespace std;
const int N = 2e5, INF = 0x3f3f3f3f3f;

int a[2][N + 5], pos[N + 5], d[2][N][32];

void RMQ_init(int n, int v) {
	for(int i = 1; i <= n; i ++) d[v][i][0] = a[v][i];
	for(int j = 1; (1 << j) <= n; j ++)
		for(int i = 1; i + (1 << j) - 1 <= n; i ++)
			d[v][i][j] = min(d[v][i][j - 1], d[v][i + (1 << (j - 1))][j - 1]);
}

int RMQ(int a, int b, int v) {
	int k = 0;
	while((1 << (k + 1)) <= b - a + 1) k ++;
	return min(d[v][a][k], d[v][b - (1 << k) + 1][k]);
}

struct node {
	int x, L, R;
	bool operator < (const node& A) const {
		return x > A.x; // 注意是 > 号 
	}
};

int main() {
	int n, x;
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++) {
		scanf("%d", &x);
		a[i & 1][i] = x;
		a[(i & 1) ^ 1][i] = INF;
		pos[x] = i;
	}
	RMQ_init(n, 0); RMQ_init(n, 1);
	priority_queue<node> Q;
	x = RMQ(1, n, 1);
	Q.push({x, 1, n});
	while(!Q.empty()) {
		node x = Q.top(); Q.pop();
		int v1 = x.x, v2 = RMQ(pos[x.x] + 1, x.R, (pos[x.x] & 1) ^ 1);
		printf("%d %d ", v1, v2);
		v1 = pos[v1], v2 = pos[v2];
		if(x.L != v1) Q.push({RMQ(x.L, v1 - 1, x.L & 1), x.L, v1 - 1});
		if(v1 + 1 != v2) Q.push({RMQ(v1 + 1, v2 - 1, (v1 + 1) & 1), v1 + 1, v2 - 1});
		if(v2 != x.R) Q.push({RMQ(v2 + 1, x.R, (v2 + 1) & 1), v2 + 1, x.R});
	}
	printf("\n");
	return 0;
}
### Prompt

Develop a solution in Cpp to the problem described below:

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

### Response

```cpp
#include <bits/stdc++.h>

using namespace std;
const int N = 2e5, INF = 0x3f3f3f3f3f;

int a[2][N + 5], pos[N + 5], d[2][N][32];

void RMQ_init(int n, int v) {
	for(int i = 1; i <= n; i ++) d[v][i][0] = a[v][i];
	for(int j = 1; (1 << j) <= n; j ++)
		for(int i = 1; i + (1 << j) - 1 <= n; i ++)
			d[v][i][j] = min(d[v][i][j - 1], d[v][i + (1 << (j - 1))][j - 1]);
}

int RMQ(int a, int b, int v) {
	int k = 0;
	while((1 << (k + 1)) <= b - a + 1) k ++;
	return min(d[v][a][k], d[v][b - (1 << k) + 1][k]);
}

struct node {
	int x, L, R;
	bool operator < (const node& A) const {
		return x > A.x; // 注意是 > 号 
	}
};

int main() {
	int n, x;
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++) {
		scanf("%d", &x);
		a[i & 1][i] = x;
		a[(i & 1) ^ 1][i] = INF;
		pos[x] = i;
	}
	RMQ_init(n, 0); RMQ_init(n, 1);
	priority_queue<node> Q;
	x = RMQ(1, n, 1);
	Q.push({x, 1, n});
	while(!Q.empty()) {
		node x = Q.top(); Q.pop();
		int v1 = x.x, v2 = RMQ(pos[x.x] + 1, x.R, (pos[x.x] & 1) ^ 1);
		printf("%d %d ", v1, v2);
		v1 = pos[v1], v2 = pos[v2];
		if(x.L != v1) Q.push({RMQ(x.L, v1 - 1, x.L & 1), x.L, v1 - 1});
		if(v1 + 1 != v2) Q.push({RMQ(v1 + 1, v2 - 1, (v1 + 1) & 1), v1 + 1, v2 - 1});
		if(v2 != x.R) Q.push({RMQ(v2 + 1, x.R, (v2 + 1) & 1), v2 + 1, x.R});
	}
	printf("\n");
	return 0;
}
```