#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
typedef pair<int,int>P;
typedef pair<int,P> PP;
const int MAX_N = 1<<18;
int N;
int val[200001];
int pos[200001];
int dat[2][2*MAX_N-1];

typedef struct SegTree{
   #define left_son (k*2+1)
   #define right_son (k*2+2)
   #define mid ((l+r)/2)
   int n;
   int type;

   void init(){
     int n_=N+10;
      n=1;
      while(n<n_)n*=2;
      REP(i,2*n-1){dat[0][i]=INT_MAX;dat[1][i]=INT_MAX;}
   }
   void update(int k,int a){
        k+=n-1;
        dat[type][k]=a;
        while(k>0){
           k=(k-1)/2;
           dat[type][k]=min(dat[type][left_son],dat[type][right_son]);
        }
   }
   int query(int a,int b,int k=0,int l=0,int r=-1){
       if(r==-1)r=n;
       if(r<=a||b<=l)return INT_MAX;
       if(a<=l&&r<=b)return dat[type][k];
       else{
           int vl=query(a,b,left_son,l,mid);
           int vr=query(a,b,right_son,mid,r);
           return min(vl,vr);
       }
   }
}Seg;


int main(){
    cin>>N;
    SegTree odd;odd.type=0;odd.init();
    SegTree even;even.type=1;even.init();
    REP(i,N){
        cin>>val[i],pos[val[i]]=i;
        if(i%2==0){
           even.update(i,val[i]);
           odd.update(i,INT_MAX);
        }else{
           even.update(i,INT_MAX);
           odd.update(i,val[i]);
        }
    }
    priority_queue<PP,vector<PP>,greater<PP> > que;
    int g=even.query(0,N);
    que.push(PP(g,P(0,N)));
    vector<int>ans;
    while(que.empty()==false){
       PP now=que.top();que.pop();
       int num=now.first;
       P rec=now.second;
       //cout<<num<<rec.first<<rec.second<<endl;
       int po=pos[num];
       int odd_flag=po%2;
       int g;
       if(odd_flag==1){
          g=even.query(po+1,rec.second);
       }else{
          g=odd.query(po+1,rec.second);
       }
       ans.push_back(num);ans.push_back(g);
       int po2=pos[g];
       even.update(po,INT_MAX);odd.update(po,INT_MAX);
       even.update(po2,INT_MAX);odd.update(po2,INT_MAX);
       {
          if(po!=rec.first){
             int f;
             if(odd_flag==1){
                f=odd.query(rec.first,po);
             }else{
                f=even.query(rec.first,po);
             }
             if(f!=INT_MAX){
                que.push(PP(f,P(rec.first,po)));
             }
          }
       }
       {
          if(po2-po!=1){
             int f;
             if(odd_flag==0){
                f=odd.query(po+1,po2);
             }else{
                f=even.query(po+1,po2);
             }
             if(f!=INT_MAX){
                que.push(PP(f,P(po+1,po2)));
             }
          }
       }
       {
          if(po2!=rec.second){
             int f;
             if(odd_flag==1){
                f=odd.query(po2,rec.second);
             }else{
                f=even.query(po2,rec.second);
             }
             if(f!=INT_MAX){
                que.push(PP(f,P(po2,rec.second)));
             }
          }
       }
    }
    
    REP(i,ans.size()){
        cout<<ans[i];
        if(i!=ans.size()-1){
           cout<<" ";
        }else{
           cout<<endl;
        }
    }
    
    return(0);
}

Measured memory_bytes: 8616