#include <iostream>
#include <climits>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <functional>
#include <memory>
using namespace std;

using vpii = vector<pair<int,int>>;
using pii = pair<int,int>;
using pipii = pair<int,pair<int,int>>;

/*
子供の頂点を求める式
k*2+1
k*2+2
親を求める式
(k-1)/2
*/

template<typename T>
class RMQ{
public:
    T arr[1000000+10];
    int n;
    
    /*
    template <>
    RMQ<std::pair<int,int>>::RMQ(int N,int a){
        for(int i = 0; i < 100000*2+10; i++)
            arr[i] = std::pair<int,int>(a,i);
            
        n = 1;
        while(n<N) n*=2;
        
    }
    */
    
    /*
    RMQ<int>(int N,int a){
        for(int i = 0; i < 100000*2+10; i++)
            arr[i] = a;
            
        n = 1;
        while(n<N) n*=2;
        
    }
    */
    
    RMQ(int N,T a){
        for(int i = 0; i < 1000000+10; i++)
            arr[i] = a;
            
        n = 1;
        while(n<N) n*=2;
        
    }
    
    T query(int a,int b){
        return query(a,b,0,0,n);
    }
    
    T query(int a,int b,int k,int l,int r){
        if(r <= a || b <= l) return INT_MAX;
        if(a <= l && r <= b) return arr[k];
        
        else{
            T vl = query(a,b,k*2+1,l , (l+r)/2);
            T vr = query(a,b,k*2+2,(l+r)/2,r);
            return min(vl,vr);
        }
        
    }
    
    void update(int k,T a){
        k += n-1;
        
        arr[k] = a;
        
        while(k > 0){
            k = (k-1)/2;
            arr[k] = min(arr[k*2+1],arr[k*2+2]);
        }
    }
private:
    
};


template <>
class RMQ<std::pair<int,int>>
{
public:
    
    using T = std::pair<int,int>;

    vector<T> arr;
    int n;
    
    RMQ(int N,int a){
        n = 1;
        while(n<N) n*=2;
        
        arr.assign(n*2,T(INT_MAX,a));
        
    }
    
    RMQ(int N){
        n = 1;
        while(n<N) n*=2;
        
        arr.assign(n*2,T(INT_MAX,-1));
    }
    
    T query(int a,int b){
        return query(a,b,0,0,n);
    }
    
    T query(int a,int b,int k,int l,int r){
        if(r <= a || b <= l) return T(INT_MAX,-1);
        if(a <= l && r <= b) return arr[k];
        
        else{
            T vl = query(a,b,k*2+1,l , (l+r)/2);
            T vr = query(a,b,k*2+2,(l+r)/2,r);
            return min(vl,vr);
        }
        
    }
    
    void update(int k,T a){
        k += n-1;
        
        arr[k] = a;
        
        while(k > 0){
            k = (k-1)/2;
            arr[k] = min(arr[k*2+1],arr[k*2+2]);
        }
    }
};

RMQ<pair<int,int>> odd(0,0);
RMQ<pair<int,int>> even(0,0);

vector<pair<int,int>> result;
int arr[2*100000+10];
priority_queue<pipii,std::vector<pipii> ,std::greater<pipii>> pq;

int main(void){
    cin.tie(0);
	ios::sync_with_stdio(false);
	
    int n;
    cin >> n;
    
    odd = RMQ<pair<int,int>>(n+2);//kisuu
    even = RMQ<pair<int,int>>(n+2);//gusuu
    
    for(int i = 0; i < n/2; i++){
        int a,b;
        cin >> a >> b;
        
        arr[i*2] = a;
        arr[i*2+1] = b;
        
        even.update(2*i,pair<int,int>(a,2*i));
        odd.update(2*i+1,pair<int,int>(b,2*i+1));
    }
    
    pq.push({0,{0,n}});
    
    while(!pq.empty()){
    
    int l = pq.top().second.first;
    int r = pq.top().second.second;
    
    //cout << l << " " << r << endl;
    
    pq.pop();
        
    pii p1;
    pii p2;
    
    if(l%2 == 0){
        p1 = even.query(l,r);
        p2 = odd.query(p1.second,r);
    }else{
        p1 = odd.query(l,r);
        p2 = even.query(p1.second,r);
    }
    
    //cout << p1.first << ":" << p1.second << endl;
    //cout << p2.first << ":" << p2.second << endl;

    result.push_back(pii(p1.first,p2.first));
    
    vector<pair<int, int>> next = {{l, p1.second}, {p1.second + 1, p2.second}, {p2.second + 1, r}};
    for(auto n: next){
        if(n.second - n.first > 1){
            pq.push(pipii(( (n.first % 2 == 0) ? even : odd ).query(n.first, n.second).first, n));
        }
    }
    }

    
    //cout << result.size() << endl;
    
    for(int i = 0; i < result.size(); i++){
        cout << result[i].first << " " << result[i].second << (i == result.size()-1 ? '\n' : ' ');
    }
    
}


Measured memory_bytes: 11944