#include <algorithm>
#include <bitset>
#include <list>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

template<class T>
ostream& operator<< (ostream& fout, const vector<T>& vec) {
  for (const auto& el : vec) {
    fout << el << ' ';
  }
  return fout;
}

template <class T>
istream& operator>> (istream& fin, vector<T>& vec) {
  for (size_t i = 0; i < vec.size(); ++i) {
    cin >> vec[i];
  }
  return fin;
}

constexpr int MAXN = 220000;
constexpr int INF = 1e9;
struct SegmentTree {
  vector<pair<int,int>> t;
  SegmentTree()
    : t(4*MAXN) {};

  pair<int,int> combine(pair<int,int> a, pair<int,int> b) {
    if (a.first < b.first)
      return a;
    if (b.first < a.first)
      return b;
    return make_pair(a.first, a.second);
  }

  void build (int a[], int v, int tl, int tr) {
    if (tl == tr)
      t[v] = make_pair (a[tl], tl);
    else {
      int tm = (tl + tr) / 2;
      build (a, v*2, tl, tm);
      build (a, v*2+1, tm+1, tr);
      t[v] = combine (t[v*2], t[v*2+1]);
    }
  }

  pair<int,int> get_max (int v, int tl, int tr, int l, int r) {
    if (l > r)
      return make_pair (INF, INF);
    if (l == tl && r == tr)
      return t[v];
    int tm = (tl + tr) / 2;
    return combine (
        get_max (v*2, tl, tm, l, min(r,tm)),
        get_max (v*2+1, tm+1, tr, max(l,tm+1), r)
        );
  }

  void update (int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr)
      t[v] = make_pair (new_val, tl);
    else {
      int tm = (tl + tr) / 2;
      if (pos <= tm)
        update (v*2, tl, tm, pos, new_val);
      else
        update (v*2+1, tm+1, tr, pos, new_val);
      t[v] = combine (t[v*2], t[v*2+1]);
    }
  }
};

int n;
list<pair<int, int>>* get_answer(int l, int r, SegmentTree& odd, SegmentTree& even) {
  //cerr << l << ' ' << r << std::endl;
  //assert((r - l + 1) % 2 == 0);
  if (r <= l) return nullptr;
  auto x = even.get_max(1, 0, n - 1, l, r);
  auto y = odd.get_max(1, 0, n - 1, x.second + 1, r);
  //std::cerr << "TAKEN: " << x.second << ' ' << y.second << '\n';
  //std::cerr << "TAKEN(v): " << x.first << ' ' << y.first<< '\n';

  list<pair<int,int>>* res = new list<pair<int, int>>{{x.first, y.first}};

  auto list0 = get_answer(l, x.second - 1, odd, even);
  auto list1 = get_answer(x.second + 1, y.second - 1, even, odd);
  auto list2 = get_answer(y.second + 1, r, odd, even);

  vector<list<pair<int, int>>*> tmp;

  if (list0) tmp.push_back(list0);
  if (list1) tmp.push_back(list1);
  if (list2) tmp.push_back(list2);

  sort(tmp.begin(), tmp.end(), [] (list<pair<int, int>>* a, list<pair<int, int>>* b) {
      return a->size() < b->size();
  });

  list<pair<int, int>> suff;
  for (auto el : tmp) {
    suff.merge(std::move(*el));
  }
  res->splice(res->end(), suff);

  return res;
};

int Solve() {
  cin >> n;
  vector<int> perm(n);
  vector<int> permo(n, MAXN);
  vector<int> perme(n, MAXN);
  for (int i = 0; i < n; ++i) {
    cin >> perm[i];
    if (i % 2 == 0) {
      perme[i] = perm[i];
    } else {
      permo[i] = perm[i];
    }
  }
  SegmentTree odd;
  odd.build(permo.data(), 1, 0, n - 1);
  SegmentTree even;
  even.build(perme.data(), 1, 0, n - 1);
  auto* res = get_answer(0, n - 1, odd, even);
  for (auto el : *res) {
    std::cout << el.first << ' ' << el.second << ' ';
  }
  std::cout << '\n';
  return 0;
}


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

  ios_base::sync_with_stdio(0);
  cin.tie(0);
  Solve();
  return 0;
}


Measured memory_bytes: 53632