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<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;
using namespace std;

#define N (1<<18)
int seg[2][1<<19];
void Init(){
  lol(i,N*2)lol(j,2)seg[j][i]=mod;
}
void Update(int i,int x,int flip){
  i+=N-1;
  seg[flip][i]=x;
  while(i){
    i=(i-1)/2;
    seg[flip][i]=min(seg[flip][i],x);
  }
}
int qry(int left,int right,int k,int a,int b,int flip){
  if(left<=a&&b<=right)return seg[flip][k];
  if(right<=a||b<=left)return mod;
  int m=(a+b)/2;
  return min(qry(left,right,k*2+1,a,m,flip),qry(left,right,k*2+2,m,b,flip));
}
int rmq(int left,int right,int flip){
  return qry(left,right+1,0,0,N,flip);
}

int n;
int p[200010];
int at[200010];

struct P{
  int valL,valR;
  int placeL,placeR;
  int left,right,flip;
  bool operator< (const P &P1)const{
    return valL<P1.valL;
  };
  bool operator> (const P &P1)const{
    return valL>P1.valL;
  };
};
priority_queue<P,vector<P>,greater<P> >Q;
void Qpush(int left,int right,int flip){
  if(left>right)return;
  int valL=rmq(left,right,flip);
  int placeL=at[valL];
  int valR=rmq(placeL,right,1-flip);
  int placeR=at[valR];
  P tmp;
  tmp.valL=valL,tmp.valR=valR;
  tmp.placeL=placeL,tmp.placeR=placeR;
  tmp.left=left,tmp.right=right,tmp.flip=flip;
  Q.push(tmp);
}

int main(){
  Init();
  cin>>n;
  lol(i,n){
    cin>>p[i];
    at[p[i]]=i;
    Update(i,p[i],i%2);
  }
  Qpush(0,n-1,0);
  bool first=true;
  while(!Q.empty()){
    P now=Q.top();Q.pop();
    if(!first)cout<<" ";first=false;
    cout<<now.valL<<" "<<now.valR;
    Qpush(now.left,now.placeL-1,now.flip);
    Qpush(now.placeL+1,now.placeR-1,1-now.flip);
    Qpush(now.placeR+1,now.right,now.flip);
  }
  cout<<endl;
  return 0;
}
