#include <bits/stdc++.h>

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

struct Range {
  int l;
  int r;
  int v;
  Range(int l, int r, int v) : l(l), r(r), v(v) {}
};

// A standard segment tree for point-update and range-get.
// Verified: AOJ-DSL2A, AOJ-DSL2B
template <typename T>
class SegmentTree {
 private:
  function<T(T, T)> merge_fn;
  T empty_value;
  vector<T> nodes;
  int num_nodes;

  // Returns the fold of overwrap between [node_l, node_r) and [l, r).
  // nodes[node_index] needs to correspond to [node_l, node_r).
  T GetRangeInternal(int node_index, int node_l, int node_r, int l, int r) {
    if (node_r <= l || r <= node_l) return empty_value;
    if (l <= node_l && node_r <= r) return nodes[node_index];
    int node_m = (node_l + node_r) / 2;
    return merge_fn(
        GetRangeInternal(2 * node_index, node_l, node_m, l, r),
        GetRangeInternal(2 * node_index + 1, node_m, node_r, l, r));
  }

 public:
  // Arguments:
  // in_merge: The function to merge two values. It should be a monoid.
  // in_empty_value: The identity of the monoid.
  // xs: The initial values.
  SegmentTree(
      function<T(T, T)> merge_fn, T empty_value, const vector<T>& xs) :
          merge_fn(merge_fn), empty_value(empty_value) {
    int n = xs.size();
    num_nodes = 1;
    while (num_nodes < n) num_nodes *= 2;
    num_nodes *= 2;
    nodes = vector<T>(num_nodes, empty_value);
    for (int i = 0; i < xs.size(); ++i) {
      nodes[num_nodes / 2 + i] = xs[i];
    }
    for (int i = num_nodes / 2 - 1; i >= 1; i--) {
      nodes[i] = merge_fn(nodes[2 * i], nodes[2 * i + 1]);
    }
  }

  // Updates the i-th element to x.
  void Update(int i, T x) {
    nodes[num_nodes / 2 + i] = x;
    for (int cur = (num_nodes / 2 + i) / 2; cur > 0; cur /= 2) {
      nodes[cur] = merge_fn(nodes[2 * cur], nodes[2 * cur + 1]);
    }
  }

  // Returns the value of the range [l, r) merged by merge_fn.
  T GetRange(int l, int r) {
    return GetRangeInternal(1, 0, num_nodes / 2, l, r);
  }

  T Get(int i) {
    return nodes[num_nodes / 2 + i];
  }
};

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

  int n;
  cin >> n;
  vector<int> ps(n);
  vector<int> v_to_i(n + 1);
  for (int i = 0; i < n; i++) {
    cin >> ps[i];
    v_to_i[ps[i]] = i;
  }

  constexpr int INF = 5E5;
  vector<int> ps1(n, INF);
  vector<int> ps2(n, INF);
  for (int i = 0; i < n; i++) {
    if (i % 2 == 0) ps1[i] = ps[i];
    else ps2[i] = ps[i];
  }

  auto min_fn = [](int x, int y) { return min(x, y); };
  SegmentTree<int> tree1(min_fn, INF, ps1);
  SegmentTree<int> tree2(min_fn, INF, ps2);

  auto make_range_fn = [&](int l, int r) -> Range {
    if (l % 2 == 0) {
      return Range(l, r, tree1.GetRange(l, r));
    } else {
      return Range(l, r, tree2.GetRange(l, r));
    }
  };

  auto compare_range_fn = [](Range r1,  Range r2) {
    return r1.v > r2.v;
  };
  priority_queue<Range, vector<Range>, decltype(compare_range_fn)> pq(compare_range_fn);
  pq.push(Range(0, n, tree1.GetRange(0, n)));

  vector<int> outputs;

  while (!pq.empty()) {
    Range range = pq.top();
    pq.pop();
    int v1 = range.v;
    int i1 = v_to_i[v1];
    outputs.push_back(range.v);

    int v2;
    if (range.l % 2 == 0) {
      v2 = tree2.GetRange(i1 + 1, range.r);
    } else {
      v2 = tree1.GetRange(i1 + 1, range.r);
    }
    int i2 = v_to_i[v2];
    outputs.push_back(v2);

    if (range.l < i1) {
      pq.push(make_range_fn(range.l, i1));
    }
    if (i1 + 1 < i2) {
      pq.push(make_range_fn(i1 + 1, i2));
    }
    if (i2 + 1 < range.r) {
      pq.push(make_range_fn(i2 + 1, range.r));
    }
  }

  for (int output : outputs) {
    cout << output << " ";
  }
  cout << endl;
}

Measured memory_bytes: 10252