#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<int,int> P;
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;


template< typename T >
struct SparseTable {
  vector< vector< T > > st;
  vector< int > lookup;
 
  SparseTable(const vector< T > &v) {
    int b = 0;
    while((1 << b) <= v.size()) ++b;
    st.assign(b, vector< T >(1 << b));
    for(int i = 0; i < v.size(); i++) {
      st[0][i] = v[i];
    }
    for(int i = 1; i < b; i++) {
      for(int j = 0; j + (1 << i) <= (1 << b); j++) {
        st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
      }
    }
    lookup.resize(v.size() + 1);
    for(int i = 2; i < lookup.size(); i++) {
      lookup[i] = lookup[i >> 1] + 1;
    }
  }
 
  inline T query(int l, int r) {
    int b = lookup[r - l];
    return min(st[b][l], st[b][r - (1 << b)]);
  }
};

int main(){
    int n;cin >> n;
    vector<P> a(n,make_pair(n+1,-1)),b(n,make_pair(n+1,-1));
    for (int i = 0; i < n; i++) {
        if(i%2){
            cin >> b[i].first;
            b[i] = make_pair(b[i].first,i);
        }
        else{
            cin >> a[i].first;
            a[i] = make_pair(a[i].first,i);
        }
    }
    SparseTable<P> st1(a),st2(b);
  	vector<int> ans;
  	priority_queue<pair<P,pair<P,bool>>,vector<pair<P,pair<P,bool>>>, greater<pair<P,pair<P,bool>>>> pq;
  	pq.push(make_pair(make_pair(0,0),make_pair(make_pair(0,n),false)));
  	while(!pq.empty()){
      	auto p = pq.top();pq.pop();
      	int l = p.second.first.first, r = p.second.first.second;
      	if(r<=l) continue;
      	bool c = p.second.second;
        if(c==0){
            P ll = st1.query(l,r);
            P rr = st2.query(ll.second+1,r);
      		ans.push_back(ll.first);
      		ans.push_back(rr.first);
            int li = ll.second, ri = rr.second;
          	P xx = st1.query(l,li);
          	P yy = st2.query(xx.second+1,li);
            pq.push(make_pair(make_pair(xx.first,yy.first),make_pair(make_pair(l,li),c)));
          	xx = st2.query(li+1,ri), yy = st1.query(xx.second+1,ri);	
            pq.push(make_pair(make_pair(xx.first,yy.first),make_pair(make_pair(li+1,ri),c^1)));
          	xx = st1.query(ri+1,r), yy = st2.query(xx.second+1,r);	
            pq.push(make_pair(make_pair(xx.first,yy.first),make_pair(make_pair(ri+1,r),c)));
        }
        else{
            P ll = st2.query(l,r);
            P rr = st1.query(ll.second+1,r);
          	ans.push_back(ll.first);
      		ans.push_back(rr.first);
            int li = ll.second, ri = rr.second;
          	P xx = st2.query(l,li);
          	P yy = st1.query(xx.second+1,li);
            pq.push(make_pair(make_pair(xx.first,yy.first),make_pair(make_pair(l,li),c)));
          	xx = st1.query(li+1,ri), yy = st2.query(xx.second+1,ri);	
            pq.push(make_pair(make_pair(xx.first,yy.first),make_pair(make_pair(li+1,ri),c^1)));
          	xx = st2.query(ri+1,r), yy = st1.query(xx.second+1,r);	
            pq.push(make_pair(make_pair(xx.first,yy.first),make_pair(make_pair(ri+1,r),c)));
        }
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << (i==n-1?"\n":" ");
    }
    return 0;
}


Measured memory_bytes: 82812