output_description: Print the lexicographically smallest permutation, with spaces in between.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      p_1 p_2 ... p_N
attempt: #include <bits/stdc++.h>
  using namespace std;
  
  typedef pair<int, int> pii;
  typedef long long ll;
  template<class T> using V = vector<T>;
  template<class T> using VV = V<V<T>>;
  
  #define pb push_back
  #define eb emplace_back
  #define mp make_pair
  #define fi first
  #define se second
  #define rep(i,n) rep2(i,0,n)
  #define rep2(i,m,n) for(int i=m;i<(n);i++)
  #define ALL(c) (c).begin(),(c).end()
  #define dump(x) cerr << #x << " = " << (x) << endl
  constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }
  
  template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; }
  template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; }
  
  template<class T, class U>
  ostream& operator<<(ostream& os, const pair<T, U>& p) {
  	os<<"("<<p.first<<","<<p.second<<")";
  	return os;
  }
  
  template<class T>
  ostream& operator<<(ostream& os, const vector<T>& v) {
  	os<<"{";
  	rep(i, v.size()) {
  		if (i) os<<",";
  		os<<v[i];
  	}
  	os<<"}";
  	return os;
  }
  
  const int SZ = 1 << 18;
  const int INF = TEN(9);
  
  struct segtree {
  	vector<pii> dat;
  
  	const pii inf = mp(INF, INF);
  
  	void init() {
  		dat.resize(SZ * 2);
  		rep(i, SZ * 2) dat[i] = inf;
  	}
  
  	void update(int pos, int x) {
  		dat[pos + SZ - 1] = mp(x, pos);
  		pos += SZ - 1;
  
  		while (pos > 0) {
  			pos = (pos - 1) / 2;
  			dat[pos] = min(dat[pos * 2 + 1], dat[pos * 2 + 2]);
  		}
  	}
  
  	pii get(int a, int b, int k = 0, int l = 0, int r = SZ) {
  		if (b <= l || r <= a) return inf;
  		if (a <= l && r <= b) return dat[k];
  		return min(get(a, b, k * 2 + 1, l, (l + r) / 2), get(a, b, k * 2 + 2, (l + r) / 2, r));
  	}
  } seg[2];
  
  int main() {
  	seg[0].init();
  	seg[1].init();
  
  	int N; cin >> N;
  	V<int> p(N);
  
  	rep(i, N) {
  		cin >> p[i];
  		seg[i % 2].update(i, p[i]);
  	}
  
  	using Data = pair<pii, pii>;
  	priority_queue<Data, vector<Data>, greater<Data>> que;
  
  	auto add = [&](int l, int r) {
  		auto p = seg[l%2].get(l, r);
  		if (l >= r || p.fi == INF) return ;
  		que.push(mp(seg[l%2].get(l, r), mp(l, r)));
  	};
  
  	add(0, N);
  	V<int> ans;
  
  	while (!que.empty()) {
  		auto p = que.top(); que.pop();
  		int val = p.fi.fi, pos = p.fi.se; 
  		int l = p.se.fi, r = p.se.se;
  
  		auto nx = seg[1-l%2].get(pos + 1, r);
  
  		ans.pb(val);
  		ans.pb(nx.fi);
  		add(l, pos);
  		add(pos + 1, nx.se);
  		add(nx.se + 1, r);
  	}
  
  	rep(i, N) printf("%d%c", ans[i], i == N - 1 ? '\n' : ' ');
   
  	return 0;
  }
problem_description: Statement
  
  Let N be a positive even number.
  
  We have a permutation of (1, 2, ..., N), p = (p_1, p_2, ..., p_N). Snuke is
  constructing another permutation of (1, 2, ..., N), q, following the procedure
  below.
  
  First, let q be an empty sequence. Then, perform the following operation until
  p becomes empty:
  
    * Select two adjacent elements in p, and call them x and y in order. Remove x and y from p (reducing the length of p by 2), and insert x and y, preserving the original order, at the beginning of q.
  
  When p becomes empty, q will be a permutation of (1, 2, ..., N).
  
  Find the lexicographically smallest permutation that can be obtained as q.
samples: [{"input": "4\n    3 2 4 1", "output": "3 1 2 4\n    \n\nThe solution above is obtained as follows:\n\np | q  \n---|---  \n(3, 2, 4, 1) | ()  \n\u2193 | \u2193  \n(3, 1) | (2, 4)  \n\u2193 | \u2193  \n() | (3, 1, 2, 4)  \n  \n* * *"}, {"input": "2\n    1 2", "output": "1 2\n    \n\n* * *"}, {"input": "8\n    4 6 3 2 8 5 7 1", "output": "3 1 2 7 4 6 8 5\n    \n\nThe solution above is obtained as follows:\n\np | q  \n---|---  \n(4, 6, 3, 2, 8, 5, 7, 1) | ()  \n\u2193 | \u2193  \n(4, 6, 3, 2, 7, 1) | (8, 5)  \n\u2193 | \u2193  \n(3, 2, 7, 1) | (4, 6, 8, 5)  \n\u2193 | \u2193  \n(3, 1) | (2, 7, 4, 6, 8, 5)  \n\u2193 | \u2193  \n() | (3, 1, 2, 7, 4, 6, 8, 5)"}]