#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <sstream>
#include <queue>

using namespace std;

#define MAX_N (1<<18)

// segtree struct
// 大体 http://arc080.contest.atcoder.jp/submissions/1530583 のパクリ

// to change データ数を2^nになるように水増しする関係で、datに絶対影響しない値(UNDEF)が必要
// 問題によってSEG_UNDEFの中身は書き換えなければならない
const int SEG_UNDEF = 11451419;

struct area{
  int s;
  int t;
  int v1;
  int v2;
};

// http://d.hatena.ne.jp/blanketsky/20070717/1184683160
struct Comparea : public binary_function<area,area,bool> {
  bool operator()(const area &a1, const area &a2) {
    if(a1.v1 != a2.v1){
      return a1.v1 > a2.v1;
    }else{
      return a1.v2 > a2.v2;
    }
    cout<<"unreachable"<<endl;
    return false; 
  }
};

struct segtree{
  int n;
  int dat[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[i] = SEG_UNDEF;
  }

  // k番目の値をaに書き換える(to change)
  void update(int k, int a){
    k += n-1;
    dat[k] = a;
    while(k > 0){
      k = (k-1)/2;
      dat[k] = min(dat[k*2+1], dat[k*2+2]);
    }
  }

  // a-bの区間におけるデータの呼び出し。
  int query(int a, int b){
    return querybody(a,b,0,0,n);
  }
  
  int querybody(int a, int b, int k, int l, int r){
    if(r <= a || b <= l) return SEG_UNDEF;
    if(a <= l && r <= b) return dat[k];
    else{
      int vl = querybody(a,b,k*2+1,l,(l+r)/2);
      int vr = querybody(a,b,k*2+2,(l+r)/2,r);
      // change
      return min(vl, vr);
    }
  }

  void show(){
    cout<<n*2-1<<"datas"<<endl;
    for(int i=0;i<n*2-1;++i){
      cout<<i<<","<<dat[i]<<endl;
    }
  }
};


int getVal(int start, int end, bool even, segtree &st){
  int num = (end-start)/2+1;
  int add = 0;
  if(even == true && start % 2 == 1){
    add = 1;
  }
  return st.query(start/2+add,start/2+num+add);
}

int main(){
  int N;
  cin >>N;
  int v2p[N+1];
  segtree oddt;
  segtree event;
  oddt.init(N/2);
  event.init(N/2);
  for(int i=0;i<N/2;++i){
    int p1,p2;
    cin >>p1 >>p2;
    event.update(i,p1);
    oddt.update(i,p2);
    v2p[p1] = i*2;
    v2p[p2] = i*2+1;
  }
  //oddt.show();
  //event.show();

  vector<int> out;
  area a;
  a.s = 0;
  a.t = N-1;
  a.v1 = getVal(a.s, a.t, true, event);
  a.v2 = getVal(v2p[a.v1]+1,a.t,false,oddt);
  
  priority_queue<area, vector<area>, Comparea > q;
  q.push(a);
  
  while(!q.empty()){
    area a = q.top();
    q.pop();
    out.push_back(a.v1);
    out.push_back(a.v2);
    //cout<<"add "<<a.v1<<","<<a.v2<<endl;
    
    if(v2p[a.v1] != a.s){
      area a2;
      a2.s = a.s;
      a2.t = v2p[a.v1]-1;
      
      a2.v1 = (a2.s%2 == 0 ? getVal(a2.s,a2.t,true,event) :  getVal(a2.s,a2.t,false,oddt));
      a2.v2 = (a2.s%2 == 0 ? getVal(v2p[a2.v1],a2.t,false,oddt) :  getVal(v2p[a2.v1],a2.t,true,event));
      //cout<<a2.s<<","<<a2.t<<","<<a2.v1<<","<<a2.v2<<","<<endl;
      q.push(a2);
    }
    if(v2p[a.v2] != a.t){
      area a2;
      a2.s = v2p[a.v2] + 1;
      a2.t = a.t;
      a2.v1 = (a2.s%2 == 0 ? getVal(a2.s,a2.t,true,event) :  getVal(a2.s,a2.t,false,oddt));
      a2.v2 = (a2.s%2 == 0 ? getVal(v2p[a2.v1],a2.t,false,oddt) :  getVal(v2p[a2.v1],a2.t,true,event));

      //cout<<a2.s<<","<<a2.t<<","<<a2.v1<<","<<a2.v2<<","<<endl;
      q.push(a2);
    }
    if(v2p[a.v2] - v2p[a.v1] > 1){
      area a2;
      if((v2p[a.v2] - v2p[a.v1])%2 != 1){
	cout<<"unreachable err"<<v2p[a.v2] <<","<<v2p[a.v1]<<","<<a.v2 <<","<<a.v1<<endl;
      }
      a2.s = v2p[a.v1] + 1;
      a2.t = v2p[a.v2] - 1;

      a2.v1 = (a2.s%2 == 0 ? getVal(a2.s,a2.t,true,event) :  getVal(a2.s,a2.t,false,oddt));
      a2.v2 = (a2.s%2 == 0 ? getVal(v2p[a2.v1],a2.t,false,oddt) :  getVal(v2p[a2.v1],a2.t,true,event));

      //cout<<a2.s<<","<<a2.t<<","<<a2.v1<<","<<a2.v2<<","<<endl;
      q.push(a2);
    }
  }
  for(int i=0;i<N;++i){
    cout<<out[i];
    if(i!=N-1){
      cout<<" ";
    }
  }
}

Measured memory_bytes: 6900