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>
#define N 200005
#define inf 1000000007
using namespace std;

int n,a[N],loc[N],st[2][N*4];

struct minh {

  int segval;
  int bas,son;

};

bool operator < (minh x,minh y) {
    return x.segval>y.segval;
}

void build(int node,int bas,int son,int mod) {

  if(bas==son) {
    if(bas%2==mod) {
      st[mod][node]=a[bas];
    }
    else {
      st[mod][node]=inf;
    }
    return ;
  }
  int orta=(bas+son)/2;
  build(node*2,bas,orta,mod);
  build(node*2+1,orta+1,son,mod);
  st[mod][node]=min(st[mod][node*2],st[mod][node*2+1]);

}

int get(int node,int bas,int son,int x,int y,int mod) {

  if(bas>y || son<x) return inf;
  if(bas>=x && son<=y) return st[mod][node];
  int orta=(bas+son)/2;
  return min(get(node*2,bas,orta,x,y,mod),get(node*2+1,orta+1,son,x,y,mod));

}

void solve() {

  priority_queue<minh> q;
  q.push({get(1,1,n,1,n,1),1,n});
  while(!q.empty()) {
    minh top=q.top();
    q.pop();
    int ar[2]={0};
    int vals[2];
    if(top.bas%2) {
      ar[0]=1;
    }
    else {
      ar[1]=1;
    }
    int bas=top.bas;
    for(int i=0;i<2;i++) {
      vals[i]=get(1,1,n,bas,top.son,ar[i]);
      bas=loc[vals[i]]+1;
      printf("%d ",vals[i]);
    }
    int ara[3][2]={top.bas,loc[vals[0]]-1,loc[vals[0]]+1,loc[vals[1]]-1,loc[vals[1]]+1,top.son};
    for(int i=0;i<3;i++) {
      if(ara[i][0]>=1 && ara[i][1]<=n && ara[i][0]<=ara[i][1]) {
        q.push({get(1,1,n,ara[i][0],ara[i][1],ara[i][0]%2),ara[i][0],ara[i][1]});
      }
    }
  }

}



int main() {

  scanf("%d",&n);
  for(int i=1;i<=n;i++) {
    scanf("%d",&a[i]);
    loc[a[i]]=i;
  }
  for(int i=0;i<2;i++) {
    build(1,1,n,i);
  }
  solve();

}