#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <functional>
#include <utility>
#include <queue>
#include <vector>
#include <string>
#include <stack>
#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;
typedef long long int ll;
const ll  MOD = 1000000007;
typedef pair<ll,ll> P;
const ll INF = 100100100100100100;
const ll N_MAX = 1 << 18;//100000 kurai

ll N, dat1[2*N_MAX-1],dat2[2*N_MAX-1];
ll p[200100];
ll taiou[200100];
ll hanten[200100];
vector<P> ans;
vector<P> kukan;
priority_queue<P> pos_to_score;

void init(ll n){
  N = 1;
  while(N < n) N*= 2;
  rep(i,2*N-1){
    dat1[i] = INF;
    dat2[i] = INF;
  }
}

//k wo a ni henko(0-indexed)
void update1(ll k , ll a){
  k += N/2-1;
  dat1[k] = a;
  while(k > 0){
    k = (k-1)/2;
    dat1[k] = min(dat1[k*2 + 1],dat1[k*2 + 2]);
  }
}

void update2(ll k , ll a){
  k += N/2-1;
  dat2[k] = a;
  while(k > 0){
    k = (k-1)/2;
    dat2[k] = min(dat2[k*2 + 1],dat2[k*2 + 2]);
  }
}

//get min of [a,b)
//query(a,b,0,0,N) de yobu
ll query1(ll a, ll b , ll k , ll l , ll r){
  if(r <= a || b <= l) return INF;
  if(a <= l && r <= b) return dat1[k];
  else{
    ll vl = query1(a,b,k*2+1,l,(l+r)/2);
    ll vr = query1(a,b,k*2+2,(l+r)/2,r);
    return min(vl,vr);
  }
}
ll query2(ll a, ll b , ll k , ll l , ll r){
  if(r <= a || b <= l) return INF;
  if(a <= l && r <= b) return dat2[k];
  else{
    ll vl = query2(a,b,k*2+1,l,(l+r)/2);
    ll vr = query2(a,b,k*2+2,(l+r)/2,r);
    return min(vl,vr);
  }
}


int main(){
  cin >> N;
  ll N2 = N;
  init(N);
  rep(i,N2){
    cin >> p[i];
    taiou[p[i]] = i/2;
    if(i%2==0){
      update1(i/2,p[i]);
    }
    else{
      update2(i/2,p[i]);
    }
  }
  kukan.push_back(make_pair(0,N2/2-1));
  pos_to_score.push(make_pair(0,0));
  ll l = 1;
  while(!pos_to_score.empty()){
    P tmp = pos_to_score.top();
    pos_to_score.pop();
    ll a = kukan[tmp.second].first;
    ll b = kukan[tmp.second].second;
    ll aa,bb;
    //cerr << a << " " << b << " tenti:"<< hanten[tmp.second] << endl;
    if(hanten[tmp.second] == 0){
      aa = query1(a,b+1,0,0,N/2);
      bb = query2(taiou[aa],b+1,0,0,N/2);
      //cerr << " " << aa << " " << bb << " " << endl;
      if(taiou[aa] > a){
        ll minscore1 = query1(a,taiou[aa],0,0,N/2);
        kukan.push_back(make_pair(a,taiou[aa]-1));
        pos_to_score.push(make_pair(-minscore1,l++));
        //cerr << "aaa" << endl;
        //cerr << "score:" << minscore1 << endl;
      }
      if(taiou[aa] != taiou[bb]){
        ll minscore2 = query2(taiou[aa],taiou[bb],0,0,N/2);
        kukan.push_back(make_pair(taiou[aa],taiou[bb]));
        hanten[l] = (hanten[tmp.second] + 1) % 2;
        pos_to_score.push(make_pair(-minscore2,l++));
        //cerr << "bbb" << endl;
        //cerr << "score:" << minscore2 << endl;
      }
      if(taiou[bb] < b){
        ll minscore3 = query1(taiou[bb]+1,b+1,0,0,N/2);
        kukan.push_back(make_pair(taiou[bb]+1,b));
        pos_to_score.push(make_pair(-minscore3,l++));
        //cerr << "ccc" << endl;
        //cerr << "score:" << minscore3 << endl;
      }
      update1(taiou[aa],INF);
      update2(taiou[bb],INF);
    }
    else{
      aa = query2(a,b,0,0,N/2);
      bb = query1(taiou[aa]+1,b+1,0,0,N/2);
      //cerr << "  " << aa << " " << bb << " " << endl;
      if(taiou[aa] > a){
        ll minscore1 = query2(a,taiou[aa],0,0,N/2);
        kukan.push_back(make_pair(a,taiou[aa]));
        hanten[l] = 1;
        pos_to_score.push(make_pair(-minscore1,l++));
        //cerr << "ddd" << endl;
        //cerr << "score:" << minscore1 << endl;
      }
      if(taiou[bb] - taiou[aa] > 1){
        ll minscore2 = query1(taiou[aa]+1,taiou[bb],0,0,N/2);
        kukan.push_back(make_pair(taiou[aa]+1,taiou[bb]-1));
        hanten[l] = 0;
        pos_to_score.push(make_pair(-minscore2,l++));
        //cerr << "eee" << endl;
        //cerr << "score:" << minscore2 << endl;
      }
      if(taiou[bb] < b){
        ll minscore3 = query2(taiou[bb],b,0,0,N/2);
        kukan.push_back(make_pair(taiou[bb],b));
        hanten[l] = 1;
        pos_to_score.push(make_pair(-minscore3,l++));
        //cerr << "fff" << endl;
        //cerr << "score:" << minscore3 << endl;
      }
      update2(taiou[aa],INF);
      update1(taiou[bb],INF);
    }
    ans.push_back(make_pair(aa,bb));
  }
  rep(i,N2/2){
  //rep(i,ans.size()){
    if(i==0) cout << ans[i].first << " " << ans[i].second;
    else cout << " " << ans[i].first << " " << ans[i].second;
  }
  cout << endl;
}


Measured memory_bytes: 17632