#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }

// ----------------------------------------------------------------------
// ----------------------------------------------------------------------

struct SegTree {
  int size;
  vector<ll> pos;
  SegTree(ll N) { size = 1; while(size<N) size<<=1; pos.resize(2*size,0); }
  ll operator[](const ll &x) const { return pos[x+size]; }

  void build() { per(i,size) operate(i); }
  void set(ll x, const ll v) { pos[x+size] = v; }
  void update(ll x, const ll v) { set(x,v); x+=size; while (x>>=1) operate(x); }
  ll query(ll a, ll b) {
    ll L = INF, R = INF;
    for (a+=size, b+=size; a<b; a>>=1, b>>=1) {
      if (a&1) { L = q(L,pos[a]); a++; }
      if (b&1) { b--; R = q(R,pos[b]); }
    }
    return q(L,R);
  }
  void operate(ll i) { pos[i] = min(pos[i*2],pos[i*2+1]); }
  ll q(ll x, ll y) { return min(x,y); }
};

// ----------------------------------------------------------------------
// ----------------------------------------------------------------------

struct seq { ll from; ll to; ll m1; ll m2; };
bool operator< (const seq &x, const seq &y){ return x.m1 > y.m1; };

int main() {
  ll N; cin >> N;
  ll p[N]; rep(i,N) cin >> p[i];
  ll pos[N+1]; rep(i,N) pos[p[i]] = i;

  SegTree st_o(N), st_e(N);
  rep(i,N) {
    if (i%2==0) st_e.update(i/2, p[i]);
    else st_o.update(i/2, p[i]);
  }

  priority_queue<seq> q;
  ll fme = st_e.query(0,N/2);
  ll fmo = st_o.query((pos[fme]+1)/2,N-N/2);
  q.push({0,N-1,fme,fmo});
  // cout << q.top().m1 << " " << q.top().m2 << endl;
  vector<int> result;
  while (q.size()) {
    seq qt = q.top(); q.pop();
    result.push_back(qt.m1); result.push_back(qt.m2);
    // cout << qt.from << " " << qt.to << " " << qt.m1 << " " << qt.m2 << endl;

    if (qt.from!=pos[qt.m1]) {
      ll le = qt.from/2, re = (pos[qt.m1]-1-qt.from%2)/2;
      ll me = qt.from%2==0 ? st_e.query(le,re+1) : st_o.query(le,re+1);
      ll lo = (pos[me]+1)/2, ro = (pos[qt.m1]-(pos[me]+1)%2)/2;
      ll mo = qt.from%2==1 ? st_e.query(lo,ro+1) : st_o.query(lo,ro+1);
      q.push({qt.from,pos[qt.m1]-1,me,mo});
    }
    if (pos[qt.m1]+1!=pos[qt.m2]) {
      ll le = (pos[qt.m1]+1)/2, re = (pos[qt.m2]-1-(pos[qt.m1]+1)%2)/2;
      ll me = (pos[qt.m1]+1)%2==0 ? st_e.query(le,re+1) : st_o.query(le,re+1);
      ll lo = (pos[me]+1)/2, ro = (pos[qt.m2]-1-(pos[me]+1)%2)/2;
      ll mo = (pos[qt.m1]+1)%2==1 ? st_e.query(lo,ro+1) : st_o.query(lo,ro+1);
      q.push({pos[qt.m1]+1,pos[qt.m2]-1,me,mo});
    }
    if (qt.to!=pos[qt.m2]) {
      ll le = (pos[qt.m2]+1)/2, re = (qt.to-(pos[qt.m2]+1)%2)/2;
      ll me = (pos[qt.m2]+1)%2==0 ? st_e.query(le,re+1) : st_o.query(le,re+1);
      ll lo = (pos[me]+1)/2, ro = (qt.to-(pos[me]+1)%2)/2;
      ll mo = (pos[qt.m2]+1)%2==1 ? st_e.query(lo,ro+1) : st_o.query(lo,ro+1);
      q.push({pos[qt.m2]+1,qt.to,me,mo});
    }
  }
  debug(all(result));
  return 0;
}

Measured memory_bytes: 15856