// Slower C++ solution:
//#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;

}


// Faster C++ solution for the same problem (measured speedup: 3.455298370204278x):
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

using PII = pair<ll, ll>;

#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()

template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }

template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }

struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;

#ifdef DEBUG_ 

#include "../program_contest_library/memo/dump.hpp"

#else

#define dump(...)

#endif

const ll INF = 1LL<<60;



template <typename Monoid>

struct lazysegtree {

    using T = typename Monoid::T;

    using E = typename Monoid::E;

    int n, height;

    vector<T> dat;

    vector<E> lazy;



    lazysegtree() {}

    lazysegtree(int n_) {

        n = 1, height = 0;

        while(n <= n_) { n *= 2; height++; }

        dat.assign(n*2, Monoid::dt());

        lazy.assign(n*2, Monoid::de());

    }

    void build(vector<T> v) {

        REP(i, v.size()) dat[i+n] = v[i];

        for(int i=n-1; i>0; --i) dat[i] = Monoid::f(dat[i*2], dat[i*2+1]);

    }



    inline T reflect(int k) { return lazy[k]==Monoid::de()?dat[k]:Monoid::g(dat[k], lazy[k]); }

    inline void eval(int k) {

        if(lazy[k] == Monoid::de()) return;

        lazy[2*k]   = Monoid::h(lazy[k*2],   lazy[k]);

        lazy[2*k+1] = Monoid::h(lazy[k*2+1], lazy[k]);

        dat[k] = reflect(k);

        lazy[k] = Monoid::de();

    }

    inline void thrust(int k) { for(int i=height;i;--i) eval(k>>i); }

    inline void recalc(int k) { while(k>>=1) dat[k] = Monoid::f(reflect(k*2), reflect(k*2+1)); }



    void update(int a, int b, E x) {

        thrust(a+=n);

        thrust(b+=n-1);

        for(int l=a, r=b+1; l<r; l>>=1,r>>=1) {

            if(l&1) lazy[l] = Monoid::h(lazy[l], x), ++l;

            if(r&1) --r, lazy[r] = Monoid::h(lazy[r], x);

        }

        recalc(a);

        recalc(b);

    }

    T query(int a, int b) {

        thrust(a+=n);

        thrust(b+=n-1);

        T vl=Monoid::dt(), vr=Monoid::dt();

        for(int l=a, r=b+1; l<r; l>>=1,r>>=1) {

            if(l&1) vl=Monoid::f(vl, reflect(l++));

            if(r&1) vr=Monoid::f(reflect(--r), vr);

        }

        return Monoid::f(vl, vr);

    }



    friend ostream &operator <<(ostream& out,const lazysegtree<Monoid>& seg) {

        out << "---------------------" << endl;

        int cnt = 1;

        for(int i=1; i<=seg.n; i*=2) {

            REP(j, i) {

                out << "(" << seg.dat[cnt] << "," << seg.lazy[cnt] << ") ";

                cnt++;

            }

            out << endl;

        }

        out << "---------------------" << endl;

        return out;

    }

};



struct update_min {

    using T = pair<PII,ll>;

    using E = ll;

    static T dt() { return T({{INF, INF}, 0}); }

    static constexpr E de() { return INF; }

    static T f(const T &a, const T &b) {

        T ret;

        if(a.first.first < b.first.first) {

            ret.first.first = a.first.first;

            ret.first.second = a.first.second;

        } else {

            ret.first.first = b.first.first;

            ret.first.second = b.first.second;

        }

        ret.second = a.second+b.second;

        return ret;

    }

    static T g(const T &a, const E &b) {

        T ret;

        ret.first.first = b;

        ret.first.second = a.first.second;

        ret.second = a.second;

        return ret;

    }

    static E h(const E &a, const E &b) {

        return b == de() ? a : b;

    }

};



int main(void) {

    ll n;

    cin >> n;

    vector<ll> p(n);

    REP(i, n) cin >> p[i];



    lazysegtree<update_min> gu(n), ki(n);

    vector<pair<PII,ll>> init_g(n), init_k(n);

    REP(i, n) {

        if(i%2==0) {

            init_g[i] = {{p[i], i}, 1};

            init_k[i] = {{INF, i}, 1};

        } else {

            init_g[i] = {{INF, i}, 1};

            init_k[i] = {{p[i], i}, 1};

        }

    }

    gu.build(init_g);

    ki.build(init_k);



    vector<ll> ans;

    using P = pair<ll,PII>;

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

    que.push({0, {0, n}});

    while(que.size()) {

        ll l, r;

        tie(l, r) = que.top().second; que.pop();

        // [l, r) の偶数番目

        PII a = (l%2==0 ? gu : ki).query(l, r).first;

        ans.push_back(a.first);

        ll idx1 = a.second; 

        // [idx+1, r) の奇数番目

        PII b = (l%2==0 ? ki : gu).query(idx1+1, r).first;

        ans.push_back(b.first);

        ll idx2 = b.second;



        // [l, idx1) [idx1+1, idx2) [idx2+1, r)

        if(l < idx1) que.push({(l%2==0 ? gu : ki).query(l, idx1).first.first, {l, idx1}});

        if(idx1+1 < idx2) que.push({((idx1+1)%2==0 ? gu : ki).query(idx1+1, idx2).first.first, {idx1+1, idx2}});

        if(idx2+1 < r) que.push({((idx2+1)%2==0 ? gu : ki).query(idx2+1, r).first.first, {idx2+1, r}});

    }



    REP(i, n) cout << ans[i] << (i==n-1 ? '\n' : ' ');

    cout << flush;



    return 0;

}