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 <algorithm>
#include <cstdio>
#include <queue>
#include <vector>
const int N = 200050;
int a[2][N];
int nxt[N];
int son[N][3];
int st[2][N][20];
void build(int n, int *A, int st[][20]) {
  for (int i = 0; i < n; ++i)
    st[i][0] = i;
  for (int j = 1, k = 2; k <= n; ++j, k <<= 1)
    for (int i = 0; i + k <= n; ++i) {
      int a = st[i][j - 1], b = st[i + k / 2][j - 1];
      st[i][j] = A[a] < A[b] ? a : b;
    }
}
int get(int *A, int st[][20], int l, int r) {
  int d = 1, k = 0;
  while ((d << 1) <= r - l + 1) d <<= 1, ++k;
  int a = st[l][k], b = st[r - d + 1][k];
  return A[a] < A[b] ? a : b;
}
int solve(int l, int r) {
  if (l > r) return -1;
  int ansl = get(a[l & 1], st[l & 1], l / 2, (r - 1) / 2);
  int ansr = get(a[~l & 1], st[~l & 1], ansl + (l & 1), r / 2);
  ansl = ansl * 2 + (l & 1), ansr = ansr * 2 + (~l & 1);
  nxt[ansl] = ansr;
  son[ansl][0] = solve(l, ansl - 1);
  son[ansl][1] = solve(ansl + 1, ansr - 1);
  son[ansl][2] = solve(ansr + 1, r);
  return ansl;
}
struct cmp{
  bool operator()(int x, int y)const{
    return a[x & 1][x >> 1] > a[y & 1][y >> 1];
  }
};
std::priority_queue<int, std::vector<int>, cmp> PQ;
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i)
    scanf("%d", &a[i & 1][i >> 1]);
  build(n >> 1, a[0], st[0]);
  build(n >> 1, a[1], st[1]);
  int root = solve(0, n - 1);
  while (!PQ.empty()) PQ.pop();
  PQ.push(root);
  while (!PQ.empty()) {
    int x = PQ.top(); PQ.pop();
    printf("%d %d ", a[x & 1][x >> 1], a[nxt[x] & 1][nxt[x] >> 1]);
    for (int i = 0; i < 3; ++i) if (~son[x][i]) PQ.push(son[x][i]);
  }
  return 0;

}