#include <bits/stdc++.h>
#define LL long long
#define FOR(i,c) for(__typeof(c.begin()) i = c.begin(); i != c.end(); i++)
#define F first
#define S second
using namespace std;

const LL mod = 1e9 + 7;

template<typename T> T gcd(T a, T b) { return b == 0?a: gcd(b, a % b); }
template<typename T> T LCM(T a, T b) { return a*(b/gcd(a, b)); }
template<typename T> T expo(T base, T e, T mod) { T res = 1;
  while(e > 0) { if(e&1) res = res * base % mod; base = base * base % mod; e >>= 1; }
  return res;
}
template<typename T, typename S> T expo(T b, S e){if(e <= 1)return e == 0?1: b;\
	return (e&1) == 0?expo((b*b), e>>1): (b*expo((b*b), e>>1));}
template<typename T, typename S> T modinv(T a, S mod) { return expo(a, mod-2, mod); }
template<class T, class S> std::ostream& operator<<(std::ostream &os, const std::pair<T, S> &t) {
	os<<"("<<t.first<<", "<<t.second<<")";
	return os;
}
template<class T> std::ostream& operator<<(std::ostream &os, const std::vector<T> &t) {
	os<<"["; FOR(it,t) { if(it != t.begin()) os<<", "; os<<*it; } os<<"]";
	return os;
}
#define gc getchar_unlocked
template <typename T> void in(T &x) {
	T c = gc(); while(((c < 48) || (c > 57)) && (c!='-')) c = gc();
	bool neg = false; if(c == '-') neg = true; x = 0; for(;c < 48 || c > 57;c=gc());
	for(;c > 47 && c < 58;c=gc())	x = (x*10) + (c - 48); if(neg)	x = -x;
}

const int MAXN = 2e5 + 100;
const int INF = 1e9;
int arr[MAXN], n;
int odd[MAXN], even[MAXN];
int pos[MAXN];

struct rmq {
  int *arr;
  int tree[MAXN*4];
  void build(int root = 1, int l = 1, int r = n) {
    tree[root] = arr[l];
    if(l == r) {
      return ;
    }
    int mid = (l + r) >> 1;
    build(root*2, l, mid);
    build(root*2+1, mid+1, r);
    tree[root] = min(tree[root*2], tree[root*2+1]);
  }
  int query(int ql, int qr, int root = 1, int l = 1, int r = n) {
    if(ql <= l && qr >= r) {
      return tree[root];
    } else if(l > qr || r < ql) {
      return INF;
    }
    int mid = (l + r) >> 1;
    int res = INF;
    res = min(res, query(ql, qr, root*2, l, mid));
    res = min(res, query(ql, qr, root*2+1, mid+1, r));
    return res;
  }
} Odd, Even, All;

struct segment {
  int l, r, minim;
  bool operator<(const segment &other) const {
    return minim < other.minim;
  }
};

int ans[MAXN];

int main() {
  in(n);
  for(int i = 1; i <= n; i++) {
    in(arr[i]);
    pos[arr[i]] = i;
    if(i % 2) {
      even[i] = INF;
      odd[i] = arr[i];
    } else {
      odd[i] = INF;
      even[i] = arr[i];
    }
  }
  All.arr = arr;
  Even.arr = even;
  Odd.arr = odd;
  All.build();
  Even.build();
  Odd.build();
  set<segment> S;
  S.insert({1, n, Odd.query(1, n - 1)});
  int iter = 0;
  while(S.size() > 0) {
    auto f = *S.begin();
    S.erase(S.begin());
    int l = f.l, r = f.r, val = f.minim, p = pos[val];
    assert(p < r);
    assert(r - l + 1 > 1);
    if(r - l == 1) {
      ans[++iter] = arr[l];
      ans[++iter] = arr[r];
    } else {
      ans[++iter] = val;
      int other = -1;
      if(p % 2) {
        other = Even.query(p + 1, r);
      } else {
        other = Odd.query(p + 1, r);
      }
      assert(other <= n && other > 0);
      int p_other = pos[other];
      ans[++iter] = other;
      if(p_other - 1 > p) {
        auto &R = (p + 1) % 2 == 0 ? Even : Odd;
        S.insert({p + 1, p_other - 1, R.query(p + 1, p_other - 2)});
      }
      if(p_other + 1 < r) {
        auto &R = (p_other + 1) % 2 == 0 ? Even : Odd;
        S.insert({p_other + 1, r, R.query(p_other + 1, r - 1)});
      }
      if(l < p) {
        auto &R = (l % 2) == 0 ? Even : Odd;
        S.insert({l, p - 1, R.query(l, p - 1)});
      }
    }
  }
  for(int i = 1; i <= n; i++) {
    printf("%d ", ans[i]);
  }
  puts("");
  return 0;
}


Measured memory_bytes: 17280