#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>
#include <iomanip>
#include <cmath>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>


//using namespace __gnu_pbds;
using namespace std;


typedef long long ll;
typedef long double ld;

/*
typedef
tree<
  int, // Data type
  null_type,
  less<int>, // Comparator function for the data type
  rb_tree_tag,
  tree_order_statistics_node_update>
ordered_set;
*/

const ll MOD_CONST = 1000000007ll;


ll modSum(ll a, ll b, ll MOD = MOD_CONST) {
  return ((a % MOD) + (b % MOD)) % MOD;
}


ll modSubtract(ll a, ll b, ll MOD = MOD_CONST) {
  return (((a % MOD) - (b % MOD)) + MOD + MOD) % MOD;
}


ll modProd(ll a, ll b, ll MOD = MOD_CONST) {
  return ((a % MOD) * (b % MOD)) % MOD;
}


ll getPowMod(ll x, ll e, ll MOD = MOD_CONST) {
  if (e == 0) return 1;
  if (e % 2 == 0) {
    ll tmp = getPowMod(x, e/2, MOD);
    return modProd(tmp, tmp);
  } else {
    ll tmp = getPowMod(x, e-1, MOD);
    return modProd(tmp, x);
  }
}


ll getPow(ll x, ll e) {
  if (e == 0) return 1;
  if (e % 2 == 0) {
    ll tmp = getPow(x, e/2);
    return tmp * tmp;
  } else {
    ll tmp = getPow(x, e-1);
    return tmp * x;
  }
}


ll getInverse(ll x, ll MOD = MOD_CONST) {
  return getPowMod(x, MOD-2, MOD);
}


bool isEven(ll x) {
  ll tmp = ((x % 2) + 2) % 2;
  return tmp == 0;
}


ll getSumOfDigitsInBase(ll n, ll b) {
  ll ret = 0;
  while (n > 0) {
    ret += n % b;
    n /= b;
  }
  return ret;
}


vector<int> getKMP(string &s) {
  int len = (int)s.size();
  vector<int> ret (len, 0);
  for (int i = 1 ; i < len ; i++) {
    int at = ret[i-1];
    while (at > 0 && s[i] != s[at]) {
      at = ret[at-1];
    }
    if (s[i] == s[at]) {
      at++;
    }
    ret[i] = at;
  }
  return ret;
}


string getSubstring(string &s, int from, int to) {
  int l = to-from+1;
  if (l <= 0) {
    return "";
  }
  return s.substr(from, l);
}

ll gcd(ll a, ll b, ll & x, ll & y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    ll x1, y1;
    ll d = gcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}


pair<ll, ll> getIntersectingRange(ll a1, ll b1, ll a2, ll b2) {
  ll s = max(a1, a2);
  ll e = min(b1, b2);

  return {s, e};
}


bool isNonEmptyIntersection(ll a1, ll b1, ll a2, ll b2) {
  auto p = getIntersectingRange(a1, b1, a2, b2);
  return p.first <= p.second;
}


double getPointDistance(double x1, double y1, double x2, double y2) {
  double dx = x1-x2;
  double dy = y1-y2;
  double d = (dx * dx) + (dy * dy);
  return sqrt(d);
}


bool isPrime(ll x) {
  if (x == 2 || x == 3 || x == 5 || x == 7) return true;
  if (x < 10) return false;
  ll till = min((ll)sqrt(x) + 1, x-1);
  for (ll i = 2 ; i <= till ; i++) {
    if (x % i == 0) {
      return false;
    }
  }
  return true;
}


const int TREE_SIZE = 1;


ll segTree[TREE_SIZE], lazyTree[TREE_SIZE];


void updateRange(int node, int start, int end, int l, int r, ll val)
{
    if(lazyTree[node] != 0)
    {
        // This node needs to be updated
        segTree[node] += (end - start + 1) * lazyTree[node];    // Update it
        if(start != end)
        {
            lazyTree[node*2] += lazyTree[node];                  // Mark child as lazyTree
            lazyTree[node*2+1] += lazyTree[node];                // Mark child as lazyTree
        }
        lazyTree[node] = 0;                                  // Reset it
    }
    if(start > end or start > r or end < l)              // Current segment is not within range [l, r]
        return;
    if(start >= l and end <= r)
    {
        // Segment is fully within range
        segTree[node] += (end - start + 1) * val;
        if(start != end)
        {
            // Not leaf node
            lazyTree[node*2] += val;
            lazyTree[node*2+1] += val;
        }
        return;
    }
    int mid = (start + end) / 2;
    updateRange(node*2, start, mid, l, r, val);        // Updating left child
    updateRange(node*2 + 1, mid + 1, end, l, r, val);   // Updating right child
    segTree[node] = segTree[node*2] + segTree[node*2+1];        // Updating root with max value
}


ll queryRange(int node, int start, int end, int l, int r)
{
    if(start > end or start > r or end < l)
        return 0;         // Out of range
    if(lazyTree[node] != 0)
    {
        // This node needs to be updated
        segTree[node] += (end - start + 1) * lazyTree[node];            // Update it
        if(start != end)
        {
            lazyTree[node*2] += lazyTree[node];         // Mark child as lazyTree
            lazyTree[node*2+1] += lazyTree[node];    // Mark child as lazyTree
        }
        lazyTree[node] = 0;                 // Reset it
    }
    if(start >= l and end <= r)             // Current segment is totally within range [l, r]
        return segTree[node];
    int mid = (start + end) / 2;
    ll p1 = queryRange(node*2, start, mid, l, r);         // Query left child
    ll p2 = queryRange(node*2 + 1, mid + 1, end, l, r); // Query right child
    return (p1 + p2);
}





















const int MAXN = 2e5+10;
const ll INF = 1e16;


int N;
ll ar[MAXN], evens[MAXN], odds[MAXN], valToPos[MAXN];
ll segTreeOdds[4*MAXN], segTreeEvens[4*MAXN];


void initSegTree(ll * arr, ll * segtree, int at, int from, int to) {
  if (from > to) {
    return;
  }
  if (from == to) {
    segtree[at] = arr[from];
    return;
  }
  int mid = (from + to) / 2;
  initSegTree(arr, segtree, 2*at, from, mid);
  initSegTree(arr, segtree, 2*at+1, mid+1, to);
  segtree[at] = min(segtree[2*at], segtree[2*at+1]);
}


ll querySegTree(ll * segtree, int at, int from, int to, int ql, int qr) {
  if (from > to) {
    return INF;
  }
  if (to < ql || qr < from) {
    return INF;
  }
  if (ql <= from && to <= qr) {
    return segtree[at];
  }
  int mid = (from + to) / 2;
  return min(querySegTree(segtree, 2*at, from, mid, ql, qr), querySegTree(segtree, 2*at+1, mid+1, to, ql, qr));
}


void updateSegTree(ll * segtree, int at, int from, int to, int pos, ll val) {
  if (from == to) {
    segtree[at] = val;
    return;
  }
  int mid = (from + to) / 2;
  if (pos <= mid) {
    updateSegTree(segtree, 2*at, from, mid, pos, val);
  } else {
    updateSegTree(segtree, 2*at+1, mid+1, to, pos, val);
  }
  segtree[at] = min(segtree[2*at], segtree[2*at+1]);
}


void input() {
  cin >> N;
  for (int i = 1 ; i <= N ; i++) {
    cin >> ar[i];
    valToPos[ar[i]] = i;
    if (i % 2 == 1) {
      odds[i] = ar[i];
      evens[i] = INF;
    } else {
      evens[i] = ar[i];
      odds[i] = INF;
    }
  }
}


void preprocess() {
  initSegTree(odds, segTreeOdds, 1, 1, N);
  initSegTree(evens, segTreeEvens, 1, 1, N);
}


void solve() {
  set < pair<ll, pair<int, int> > > Q;
  Q.insert({querySegTree(segTreeOdds, 1, 1, N, 1, N), {1, N}});
  while (!Q.empty()) {
    int l = Q.begin()->second.first;
    int r = Q.begin()->second.second;
    //cerr << "L = " << l << ", R = " << r << "\n";
    Q.erase(Q.begin());
    int idL, idR;
    ll v1 , v2;
    if (l % 2 == 1) {
      v1 = querySegTree(segTreeOdds, 1, 1, N, l, r);
      idL = valToPos[v1];
      v2 = querySegTree(segTreeEvens, 1, 1, N, idL, r);
      idR = valToPos[v2];
      //updateSegTree(segTreeOdds, 1, 1, N, idL, INF);
      //updateSegTree(segTreeEvens, 1, 1, N, idR, INF);
    } else {
      v1 = querySegTree(segTreeEvens, 1, 1, N, l, r);
      idL = valToPos[v1];
      v2 = querySegTree(segTreeOdds, 1, 1, N, idL, r);
      idR = valToPos[v2];
      //updateSegTree(segTreeEvens, 1, 1, N, idL, INF);
      //updateSegTree(segTreeOdds, 1, 1, N, idR, INF);
    }
    //cerr << "V1 = " << v1 << ", V2 = " << v2 << ", idL = " << idL << ", idR = " << idR << "\n";
    
    cout << v1 << " " << v2 << " ";

    if (idL + 1 < idR-1) {
      //cerr << "Putting stuff in between\n";
      if ((idL+1) % 2 == 1) {
        Q.insert({querySegTree(segTreeOdds, 1, 1, N, idL+1, idR-1), {idL+1, idR-1}});
      } else {
        Q.insert({querySegTree(segTreeEvens, 1, 1, N, idL+1, idR-1), {idL+1, idR-1}});
      }
    }
    if (l < idL) {
      //cerr << "Putting stuff before\n";
      if (l % 2 == 1) {
        Q.insert({querySegTree(segTreeOdds, 1, 1, N, l, idL-1), {l, idL-1}});
      } else {
        Q.insert({querySegTree(segTreeEvens, 1, 1, N, l, idL-1), {l, idL-1}});
      }
    }
    if (idR + 1 < r) {
      //cerr << "Putting stuff after\n";
      if ((idR+1) % 2 == 1) {
        Q.insert({querySegTree(segTreeOdds, 1, 1, N, idR+1, r), {idR+1, r}});
      } else {
        Q.insert({querySegTree(segTreeEvens, 1, 1, N, idR+1, r), {idR+1, r}});
      }
    }
  }
}



int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cerr.tie(0);

  int T;
//  cin >> T;
  T = 1;

  for (int i = 0 ; i < T ; i++) {
    input();
    preprocess();
    solve();
  }

  return 0;
}






Measured memory_bytes: 22784