#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define nfor(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define fore(i, l, r) for (int i = int(l); i < int(r); i++)
#define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
#define all(a) (a).begin(), (a).end()
#define sz(a) int((a).size())
#define pb(a) push_back(a)
#define mp(x, y) make_pair((x), (y))
#define x first
#define y second

using namespace std;

typedef long long li;
typedef long double ld;
typedef pair<int, int> pti;

template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

template<typename A, typename B> inline ostream& operator<< (ostream& out, const pair<A, B>& p) { return out << "(" << p.x << ", " << p.y << ")"; }
template<typename T> inline ostream& operator<< (ostream& out, const vector<T>& a) { out << "["; forn(i, sz(a)) { if (i) out << ','; out << ' ' << a[i]; } return out << " ]"; }
template<typename T> inline ostream& operator<< (ostream& out, const set<T>& a) { return out << vector<T>(all(a)); }
template<typename X, typename Y> inline ostream& operator<< (ostream& out, const map<X, Y>& a) { return out << vector<pair<X, Y>>(all(a)); }
template<typename T> inline ostream& operator<< (ostream& out, const pair<T*, int>& a) { return out << vector<T>(a.x, a.x + a.y); }

inline ld gett() { return ld(clock()) / CLOCKS_PER_SEC; }

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;

#ifdef SU1
#define GEN
#ifndef GEN
#define LOG
#endif
#endif

const int N = 200200;

int n, p[N];

bool read() {
#ifdef GEN
  n = 200000;
  forn(i, n) p[i] = i + 1;
  random_shuffle(p, p + n);
  return true;
#endif
  if (!(cin >> n)) return false;
  forn(i, n) assert(scanf("%d", &p[i]) == 1);
  assert(n % 2 == 0);
  return true;
}

pti t[2][4 * N];

void build(int v, int l, int r) {
  if (l + 1 == r) {
    forn(p, 2)
      t[p][v] = (l & 1) == p ? mp(::p[l], l) : mp(INF, -1);
  } else {
    int md = (l + r) >> 1;
    build(2 * v + 1, l, md);
    build(2 * v + 2, md, r);
    forn(p, 2)
      t[p][v] = min(t[p][2 * v + 1], t[p][2 * v + 2]);
  }
}

pti min(int p, int v, int l, int r, int lf, int rg) {
  if (lf >= rg) return pti(INF, -1);
  if (l == lf && r == rg) return t[p][v];
  int md = (l + r) >> 1;
  pti ans = min(p, 2 * v + 1, l, md, lf, min(md, rg));
  ans = min(ans, min(p, 2 * v + 2, md, r, max(lf, md), rg));
  return ans;
}

int tsz;
pti val[N];
vector<int> g[N];

int build(int lf, int rg) {
  if (lf >= rg) {
    assert(lf == rg);
    return -1;
  }
  assert((rg - lf) % 2 == 0);

  int x = min(lf & 1, 0, 0, n, lf, rg).y;
  assert(x != -1);
  int y = min((~lf) & 1, 0, 0, n, x, rg).y;
  assert(y != -1);
  assert(lf <= x && x < y && y < rg);

  int v = tsz++;
  val[v] = mp(p[x], p[y]);

  int nt[] = { build(lf, x), build(x + 1, y), build(y + 1, rg) };
  forn(i, 3) if (nt[i] != -1) g[v].pb(nt[i]);

  return v;
}

void solve() {
  forn(i, N) g[i].clear();
  tsz = 0;

  build(0, 0, n);
  int root = build(0, n);
  assert(root != -1);

  vector<int> ans;
  set<pair<pti, int>> z;
  z.insert(mp(val[root], root));
  while (!z.empty()) {
    int v = z.begin()->y;
    z.erase(z.begin());
    ans.pb(val[v].x);
    ans.pb(val[v].y);
    for (auto to : g[v]) z.insert(mp(val[to], to));
  }
  assert(sz(ans) == n);

  forn(i, sz(ans)) {
    if (i > 0) putchar(' ');
    printf("%d", ans[i]);
  }
  puts("");
}

int main() {
#ifdef SU1
  assert(freopen("input.txt", "rt", stdin));
  //assert(freopen("output.txt", "wt", stdout));
#endif

  cout << setprecision(10) << fixed;
  cerr << setprecision(5) << fixed;

  while (read()) {
    ld stime = gett();
    solve();
#ifdef SU1
    cerr << "Time: " << gett() - stime << endl;
#endif
    //break;
  }

  return 0;
}


Measured memory_bytes: 30964