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>
using namespace std;
const int N = 200010, MP = 20, INF = 0x3f3f3f3f;
int mn[2][N][MP],n,p[N],ln[N],val[2][N],ans[N],cnt;
struct data {
  int l,r,val,sgn;
};
struct cmp {
  bool operator () (const data& a,const data& b) {
    return p[a.val] > p[b.val];
  }
};
priority_queue<data,vector<data>,cmp> q;
int query(int sgn,int l,int r) {
  int len = ln[r - l + 1];
  return val[sgn][mn[sgn][r][len]] < val[sgn][mn[sgn][l + (1 << len) - 1][len]] ? \
    mn[sgn][r][len] : mn[sgn][l + (1 << len) - 1][len];
}
void qpush(int l,int r,int sgn) {
  q.push((data) {l,r,query(sgn,l,r),sgn});
}
int main() {
  scanf("%d",&n);
  for (int i = 1 ; i <= n ; ++ i)
    scanf("%d",&p[i]);
  for (int i = 1 ; i <= n ; ++ i) {
    val[0][i] = val[1][i] = INF;
    val[i&1][i] = p[i];
  }
  for (int k = 0 ; k <= 1 ; ++ k) {
    for (int i = 1 ; i <= n ; ++ i) {
      mn[k][i][0] = i;
      for (int j = 1 ; (1 << j) <= i ; ++ j) {
	mn[k][i][j] = val[k][mn[k][i][j-1]] < val[k][mn[k][i - (1 << j >> 1)][j-1]] ? \
					      mn[k][i][j-1] : mn[k][i - (1 << j >> 1)][j-1];
      }
    }
  }
  for (int i = 2 ; i <= n ; i <<= 1) ln[i] ++;
  for (int i = 2 ; i <= n ; ++ i) ln[i] += ln[i-1];
  qpush(1,n,1);
  for (int i = 1 ; i <= n ; i += 2) {
    data tmp = q.top();
    q.pop();
    ans[++cnt] = p[tmp.val];
    int ne = query(tmp.sgn^1,tmp.val+1,tmp.r);
    ans[++cnt] = p[ne];
    if (tmp.val > tmp.l)
      qpush(tmp.l,tmp.val-1,tmp.sgn);
    if (tmp.val + 1 < ne)
      qpush(tmp.val+1,ne-1,tmp.sgn^1);
    if (ne < tmp.r)
      qpush(ne+1,tmp.r,tmp.sgn);
  }
  for (int i = 1 ; i <= n ; ++ i)
    printf("%d ",ans[i]);
  puts("");
  return 0;
}