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;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;
 
const int MAX_N=1<<19;
const int INF=202020;
 
int n, dat[2][2*MAX_N-1];
 
void init(int n_){
  n=1;
  while(n<n_) n*=2;
  for(int i=0;i<=2*n-1;i++) dat[0][i]=dat[1][i]=INF;
}
 
void update(int k, int a,int p){
  k+=n-1;
  dat[p][k]=a;
  while(k>0){
    k=(k-1)/2;
    dat[p][k]=min(dat[p][k*2+1],dat[p][k*2+2]);
  }
}
 
int query(int a, int b, int k, int l, int r,int p){
  if(r<=a || b<=l) return INF;
  if(a<=l && r<=b) return dat[p][k];
  else{
    int vl=query(a,b,k*2+1,l,(l+r)/2,p);
    int vr=query(a,b,k*2+2,(l+r)/2,r,p);
    return min(vl,vr);
  }
}

int pos[202020],N,P[202020];

pair<int,int> cal(int l, int r){
  int x=query(l,r+1,0,0,n,l%2);
  int y=query(pos[x],r+1,0,0,n,(l+1)%2);
  return {-x,-y};
}
 
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  
  cin>>N;
  init(N);
  rep(i,N){
    cin>>P[i];
    pos[P[i]]=i;
    update(i,P[i],i%2);
  }
  priority_queue<pair<pair<int,int>,pair<int,int> > > pq;
  pq.push({cal(0,N-1),{0,N-1}});
  while(pq.size()){
    auto t=pq.top(); pq.pop();
    int x=-t.first.first;
    int y=-t.first.second;
    cout<<x<<" "<<y<<" ";
    int l=t.second.first;
    int r=t.second.second;
    x=pos[x], y=pos[y];
    if(l<x-1){
      pq.push({cal(l,x-1),{l,x-1}});
    }
    if(x+1<y-1){
      pq.push({cal(x+1,y-1),{x+1,y-1}});
    }
    if(y+1<r){
      pq.push({cal(y+1,r),{y+1,r}});
    }
  }
  cout<<endl;
  return 0;
}