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 <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

const int MAX_N = 200005;

int N, P[MAX_N], mn[MAX_N * 4][2];

int _min(int x, int y) {
  return P[x] < P[y] ? x : y;
}

void build(int x, int l, int r) {
  if (l == r) {
    mn[x][l & 1] = l;
    return;
  }
  int mid = (l + r) >> 1;
  build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
  mn[x][0] = _min(mn[x << 1][0], mn[x << 1 | 1][0]);
  mn[x][1] = _min(mn[x << 1][1], mn[x << 1 | 1][1]);
}

int query(int x, int L, int R, int l, int r, int op) {
  if (l <= L && R <= r)
    return mn[x][op];
  int mid = (L + R) >> 1, mn = 0;
  if (mid >= l) mn = query(x << 1, L, mid, l, r, op);
  if (mid < r) mn = _min(mn, query(x << 1 | 1, mid + 1, R, l, r, op));
  return mn;
}

class Data {
public:
  int l, r, k1, k2;
  inline friend bool operator < (const Data &a, const Data &b) {
    return P[a.k1] > P[b.k1];
  }
  Data() { }
  Data(int L, int R) {
    l = L, r = R;
    k1 = query(1, 1, N, l, r, l & 1);
    k2 = query(1, 1, N, k1, r, (l & 1) ^ 1);
  }
} ;

priority_queue<Data> Q;

int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; ++i) 
    scanf("%d", &P[i]);
  
  P[0] = N + 1;
  
  build(1, 1, N);

  Data x = Data(1, N);

  Q.push(x);

  while (!Q.empty()) {
    Data x = Q.top();
    Q.pop();
    printf("%d %d ", P[x.k1], P[x.k2]);

    if (x.k1 > x.l) Q.push(Data(x.l, x.k1 - 1));
    if (x.k1 < x.k2 - 1) Q.push(Data(x.k1 + 1, x.k2 - 1));
    if (x.k2 < x.r) Q.push(Data(x.k2 + 1, x.r));
  }
  puts("");
  return 0;
}
