#include <bits/stdc++.h>
#include <chrono> 
 
using namespace std;
using namespace std::chrono; 
 
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
// #pragma optimization_level 3
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define f0r(a, b) for (long long a = 0; a < (b); ++a)
#define f1r(a, b, c) for (long long a = (b); a < (c); ++a)
#define f0rd(a, b) for (long long a = (b); a >= 0; --a)
#define f1rd(a, b, c) for (long long a = (b); a >= (c); --a)
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define pb push_back
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL); cout.tie(NULL);}
#define fix(prec) {cout << setprecision(prec) << fixed;}
#define mp make_pair
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define readgraph(list, edges) for (int i = 0; i < edges; i++) {int a, b; cin >> a >> b; a--; b--; list[a].pb(b); list[b].pb(a);}
#define ai(a, n) for (int ele = 0; ele < n; ele++) cin >> a[ele];
#define ain(a, lb, rb) for (int ele = lb; ele <= rb; ele++) cin >> a[ele];
#define ao(a, n) {for (int ele = 0; ele < (n); ele++) { if (ele) cout << " "; cout << a[ele]; } cout << '\n';}
#define aout(a, lb, rb) {for (int ele = (lb); ele <= (rb); ele++) { if (ele > (lb)) cout << " "; cout << a[ele]; } cout << '\n';}
#define vsz(x) ((long long) x.size())
typedef long long ll;
typedef double ld;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
 
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
  cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
  cin >> p.first;
  return cin >> p.second;
}
 
// mt19937 rng(steady_clock::now().time_since_epoch().count());
mt19937 rng(61378913);
/* usage - just do rng() */
 
void usaco(string filename) {
  // #pragma message("be careful, freopen may be wrong")
	freopen((filename + ".in").c_str(), "r", stdin);
	freopen((filename + ".out").c_str(), "w", stdout);
}
 
const lld pi = 3.14159265358979323846;
const ll mod = 1000000007;
// const ll mod = 998244353;
// ll mod;
 
 template <typename num_t> 
struct segtree {
  int n, depth;
  vector<num_t> tree, lazy;

  void init(int s, long long* arr, bool f) {
    n = s;
    tree = vector<num_t>(4 * s, 0);
    lazy = vector<num_t>(4 * s, 0);
    init(0, 0, n - 1, arr, f);
  }

  num_t init(int i, int l, int r, long long* arr, bool f) {
    if (l == r) {
      return tree[i] = num_t(arr[l], 2 * l + f);
    }

    int mid = (l + r) / 2;
    num_t a = init(2 * i + 1, l, mid, arr, f),
          b = init(2 * i + 2, mid + 1, r, arr, f);
    return tree[i] = a.op(b);
  }

  void update(int l, int r, num_t v) {
    update(0, 0, n - 1, l, r, v);
  }

  num_t update(int i, int tl, int tr, int ql, int qr, num_t v) {
    eval_lazy(i, tl, tr);

    if (ql <= tl && tr <= qr) {
      lazy[i] = lazy[i].val + v.val;
      eval_lazy(i, tl, tr);
      return tree[i];
    }
    if (tl > tr || tr < ql || qr < tl) return tree[i];
    if (tl == tr) return tree[i];

    int mid = (tl + tr) / 2;
    num_t a = update(2 * i + 1, tl, mid, ql, qr, v),
          b = update(2 * i + 2, mid + 1, tr, ql, qr, v);
    return tree[i] = a.op(b);
  }

  num_t query(int l, int r) {
    return query(0, 0, n-1, l, r);
  }

  num_t query(int i, int tl, int tr, int ql, int qr) {
    eval_lazy(i, tl, tr);
    
    if (ql <= tl && tr <= qr) return tree[i];
    if (tl > tr || tr < ql || qr < tl) return num_t::null_v;

    int mid = (tl + tr) / 2;
    num_t a = query(2 * i + 1, tl, mid, ql, qr),
          b = query(2 * i + 2, mid + 1, tr, ql, qr);
    return a.op(b);
  }

  /* varies by implementation */
  /* this one is for range additions */
  void eval_lazy(int i, int l, int r) {
    /* special part */
    tree[i] = tree[i].lazy_op(lazy[i], (r - l + 1));
    if (l != r) {
      lazy[i * 2 + 1] = lazy[i].val + lazy[i * 2 + 1].val;
      lazy[i * 2 + 2] = lazy[i].val + lazy[i * 2 + 2].val;
    }
    /* end special part */

    lazy[i] = num_t();
  }
};

struct min_t {
  long long val;
  int ind;
  static const long long null_v = 9223372036854775807LL;

  min_t(): val(0) {}
  min_t(long long v): val(v) {}
  min_t(long long v, int i): val(v), ind(i) {};

  min_t op(min_t& other) {
    if (other.val == val) 
      return (ind > other.ind) ? other : *this;
    return (val > other.val) ? other : *this;
  }
  
  min_t lazy_op(min_t v, int size) {
    return min_t(val + v.val, ind);
  }
};
 
ll n, m, k, q, l, r, x, y, z;
ll a[1000005];
ll b[1000005];
ll c[1000005];
string s, t;
ll ans = 0;

segtree<min_t> ev, od;

int GPT;

pll eq(ll l, ll r) {
  min_t v = ev.query((l + 1) / 2, r / 2);
  return mp(v.val, v.ind);
}

pll oq(ll l, ll r) {
  min_t v = od.query(l / 2, (r - 1) / 2);
  return mp(v.val, v.ind);
}

pll get(ll l, ll r) {
  if (l % 2 == 0) {
    pll v = eq(l, r);
    pll ov = oq(v.s + 1, r);
    return mp(v.s, ov.s);
  } else {
    pll v = oq(l, r);
    pll ov = eq(v.s + 1, r);
    return mp(v.s, ov.s);
  }
}

pll preview(ll l, ll r) {
  pll x = get(l, r);
  if (x.f > x.s) swap(x.f, x.s);
  return x;
}

void solve(int tc) {
  cin >> n;
  ai(a, n);

  f0r(i, n / 2) {
    b[i] = a[2 * i];
    c[i] = a[2 * i + 1];
  }
  ev.init(n / 2, b, 0);
  od.init(n / 2, c, 1);

  vpl vals;
  priority_queue<pair<pll, pll> > pq;
  pll pv = preview(0, n - 1);
  pq.push(mp(mp(-a[pv.f], -a[pv.s]), mp(0, n - 1)));
  
  while (!pq.empty()) {
    pair<pll, pll> top = pq.top();
    pq.pop();
    vals.pb(top.f);

    ll l = top.s.f, r = top.s.s;
    pll cur = preview(l, r);

    vpl ivals;
    if (cur.f - l > 1) ivals.pb(mp(l, cur.f - 1));
    if (cur.s - cur.f > 2) ivals.pb(mp(cur.f + 1, cur.s - 1));
    if (r - cur.s > 1) ivals.pb(mp(cur.s + 1, r));

    for (pll v: ivals) {
      // cout << v << endl;
      pll pv = preview(v.f, v.s);
      pq.push(mp(mp(-a[pv.f], -a[pv.s]), mp(v.f, v.s)));
    }
  }

  for (pll x: vals) {
    cout << -x.f << " " << -x.s << " ";
  }
  cout << '\n';
}
 
int main() {
  send help
 
  // usaco("cowland");
 
  int tc = 1;
  // cin >> tc;
  for (int t = 0; t < tc; t++) solve(t);
} 

Measured memory_bytes: 35668