#include <cstdio>

#include <cstring>

#include <string>
#include <vector>
#include <algorithm>

#include <queue>

#include <cassert>

using namespace std;

#define SZ(a) int((a).size())
#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)

typedef long long llong;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> II;

const int INF = 1000000;
const int NEUTRAL_VAL = INF;
struct SegmentTreeNode {
   II val0, val1;

   SegmentTreeNode(II _val0 = II(INF, INF), II _val1 = II(INF, INF))
     : val0(_val0), val1(_val1) { }

   SegmentTreeNode operator+(const SegmentTreeNode& pR) const {
      SegmentTreeNode res( min(val0, pR.val0),
                           min(val1, pR.val1) );
      return res;
   }
};


class SegmentTree {
   int N;
   vector<SegmentTreeNode> tree;

   void _build(const vector<int>& A, int node, int L, int R);
   void _update(int idx, int val, int node, int L, int R);
   SegmentTreeNode _query(int p, int q, int node, int L, int R) const;

public:
   SegmentTree(const vector<int>& A) {
      N = A.size();
      int NUM_NODES = 4*N;
      tree = vector<SegmentTreeNode>(NUM_NODES);
      _build(A, 1, 0, N-1);
   }

   SegmentTreeNode query(int p, int q) {
      return _query(p, q, 1, 0, N-1);
   }

};

void SegmentTree::_build(const vector<int>& A, int node, int L, int R) {
   if (L == R) {
      tree[node] = SegmentTreeNode( (L & 1) == 0 ? II(A[L], L) : II(INF, INF),
                                    (L & 1) != 0 ? II(A[L], L) : II(INF, INF) );
      return;
   }

   _build(A, 2*node, L, (L+R)/2);
   _build(A, 2*node+1, (L+R)/2+1, R);

   const SegmentTreeNode& pL = tree[2*node];
   const SegmentTreeNode& pR = tree[2*node+1];

   tree[node] = pL + pR;
}


SegmentTreeNode SegmentTree::_query(int p, int q, int node, int L, int R) const {
   if (p > R || q < L)
      return SegmentTreeNode();

   if (p <= L && R <= q)
      return tree[node];

   SegmentTreeNode pL = _query(p, q, 2*node, L, (L+R)/2);
   SegmentTreeNode pR = _query(p, q, 2*node+1, (L+R)/2+1, R);

   return pL + pR;
}


struct Interval {
   int L, R;
   int min_val;
   int min_pos0, min_pos1;
   bool operator<(const Interval& it) const {
      return min_val > it.min_val;
   }
};

Interval create_new_interval(SegmentTree& st, int L, int R) {
   Interval res;
   res.L = L;
   res.R = R;
   auto x = st.query(L, R);
   if (L & 1) {
      auto y = st.query(x.val1.second+1, R);
      res.min_val  = x.val1.first;
      res.min_pos0 = x.val1.second;
      res.min_pos1 = y.val0.second;
   }
   else {
      auto y = st.query(x.val0.second+1, R);
      res.min_val  = x.val0.first;
      res.min_pos0 = x.val0.second;
      res.min_pos1 = y.val1.second;
   }
   return res;
}

VI solve(int N, const VI& P) {
   SegmentTree st(P);

   priority_queue<Interval> pq;
   pq.push( create_new_interval(st, 0, N-1) );

   VI res;
   while (SZ(res) < N) {
      Interval it = pq.top();
      pq.pop();

      res.push_back(P[it.min_pos0]);
      res.push_back(P[it.min_pos1]);

      //fprintf(stderr, "L:%d  R:%d  m0:%d  m1:%d\n", it.L, it.R, it.min_pos0, it.min_pos1);

      if (it.min_pos0-it.L > 1) {
         pq.push( create_new_interval(st, it.L, it.min_pos0-1) );
      }

      if (it.min_pos1-it.min_pos0 > 1) {
         pq.push( create_new_interval(st, it.min_pos0+1, it.min_pos1-1) );
      }

      if (it.R - it.min_pos1 > 1) {
         pq.push( create_new_interval(st, it.min_pos1+1, it.R) );
      }
   }

   return res;
}

int main(int argc, char* argv[]) {
   int N;
   scanf("%d", &N);
   VI P(N);
   REP(i, N)
      scanf("%d", &P[i]);

   VI res = solve(N, P);
   REP(i, SZ(res)) {
      if (i > 0) printf(" ");
      printf("%d", res[i]);
   }
   printf("\n");

   return 0;
}


Measured memory_bytes: 16148