// Original C++ solution (slower):
//#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;



class SegmentTree {

private:

  int size_;

  vector<PII> dat;



  PII calc(PII d1, PII d2) {return min(d1, d2);}

  PII query(int a, int b, int k, int l, int r) {

    if(r <= a || b <= l) return {INT_MAX, INT_MAX};

    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) {

    for(size_ = 1; size_ < n; size_ *= 2);

    dat.assign(2*size_-1, {INT_MAX, INT_MAX});

  }



  void update(int k, PII a) {

    k += size_ - 1;

    dat[k] = a;

    while(k > 0) {

      k = (k-1) / 2;

      dat[k] = calc(dat[k*2+1], dat[k*2+2]);

    }

  }



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

};



SegmentTree seg[2];

vector<PII> piece;

VI nxt[100010];

map<PII, int> toId;



void func(int l, int r, int par) {

  if(l >= r) return;



  PII a = seg[l%2].query(l, r-1),

      b = seg[(l+1)%2].query(a.second+1, r);



  if(par != -1) nxt[par].PB(piece.size());

  toId[{a.first, b.first}] = piece.size();

  piece.PB({a.first, b.first});



  int cur = piece.size() - 1;

  if(l < a.second) func(l, a.second, cur);

  func(a.second+1, b.second, cur);

  if(b.second+1 < r) func(b.second+1, r, cur);

}



signed main(void)

{

  int nn;

  cin >> nn;

  seg[0] = seg[1] = SegmentTree(nn);

  REP(i, nn) {

    int p; cin >> p;

    seg[i%2].update(i, {p, i});

  }

  func(0, nn, -1);



  VI ans;

  priority_queue<PII, vector<PII>, greater<PII>> que;

  que.push(piece[0]);



  while(que.size()) {

    PII p = que.top(); que.pop();

    ans.PB(p.first);

    ans.PB(p.second);

    for(int i: nxt[toId[p]]) que.push(piece[i]);

  }

  REP(i, ans.size()) {

    cout << ans[i];

    if(ans.size()-1 != i) cout << " ";

  }

  cout << endl;



  return 0;

}


// Optimized solution to the same problem (faster):
//#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;

}


// Fastest known solution for this problem: