//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

const int MAX_N = 1<<20;

template<class T>
class SegmentTree {
private:
  int size_;
  vector<T> dat;
  T init__;

  T calc(T d1, T d2) {
    return min(d1, d2);     // minnimum
    // return max(d1, d2);  // maximum
    // return d1+d2;        // sum
  }
  T query(int a, int b, int k, int l, int r) {
    if(r <= a || b <= l) return init__;
    if(a <= l && r <= b) return dat[k];
    return calc(query(a, b, 2*k+1, l, (l+r)/2),
                  query(a, b, 2*k+2, (l+r)/2, r));
  }

public:
  SegmentTree() {}
  SegmentTree(int n) {
    init__ = {INT_MAX, INT_MAX};  // 初期化用のを指定！！！
    for(size_ = 1; size_ < n; size_ *= 2);
    dat.assign(2*size_-1, init__);
  }

  void update(int k, PII a) {
    k += size_ - 1;
    dat[k] = a;      // max or min
    // dat[k] += a;  // sum
    while(k > 0) {
      k = (k-1) / 2;
      dat[k] = calc(dat[k*2+1], dat[k*2+2]);
    }
  }

  T query(int a, int b) {return query(a, b, 0, 0, size_);}

  int size() {return size_;}

  void debug() {
    int num = 1, nn = 0;
    REP(i, 2*size_-1) {
      cout << dat[i].first << "," << dat[i].second << " ";
      if(i == nn) {cout << endl; num *= 2; nn += num;}
    }
  }
};

SegmentTree<PII> seg[2];
int p[200010];

struct node {
  int l, r, m1, m2, v1, v2;
  bool operator < (const node d) const { return v1 > d.v1;}
};

node getNode(int l, int r) {
  // cout << "l:" << l << " r:" << r << endl;
  int m1, m2;
  if(l%2) {
    m1 = seg[1].query(l, r).second;
    m2 = seg[0].query(m1+1, r).second;
  } else {
    m1 = seg[0].query(l, r).second;
    m2 = seg[1].query(m1+1, r).second;
  }
  // cout << l << " " << r << " " << m1 << " " << m2 << endl;
  return (node){l, r, m1, m2, p[m1], p[m2]};
}

signed main(void)
{
  int nn;
  cin >> nn;
  seg[0] = seg[1] = SegmentTree<PII>(nn);
  REP(i, nn) {
    cin >> p[i];
    seg[i%2].update(i, {p[i], i});
  }

  // seg[0].debug();
  // seg[1].debug();

  VI ans;
  priority_queue<node> que;
  int m1 = seg[0].query(0, nn).second, m2 = seg[1].query(m1+1, nn).second;
  // cout << m1 << " " << m2 << endl;
  que.push({0, nn, m1, m2, p[m1], p[m2]});
  while(que.size()) {
    node nd = que.top(); que.pop();
    // cout << nd.l << " " << nd.r << " " << nd.m1 << " " << nd.m2 << endl;
    ans.PB(nd.v1); ans.PB(nd.v2);
    if(nd.m1 > nd.l ) {
      // cout << "a ";
      que.push(getNode(nd.l, nd.m1));
    }
    if(nd.m2 > nd.m1+1 ) {
      // cout << "b ";
      que.push(getNode(nd.m1+1, nd.m2));
    }
    if(nd.r > nd.m2+1 ) {
      // cout << "c ";
      que.push(getNode(nd.m2+1, nd.r));
    }
  }

  REP(i, ans.size()) {
    cout << ans[i];
    if(i != ans.size() - 1) cout << " ";
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 13236