#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B;
string S, T;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
typedef pair<ll,ll> P;

int main() {
    class SEGTREE{
            ll n, dflt;
      		vector<ll> dat;
        public:
        	SEGTREE(unsigned long _n, ll _a) : dat(_n * 4, _a){
        	    n = 1;
        	    dflt = _a;
        	    while(n < _n) n *= 2;
            }
            void update(ll k, ll a){
                k += n;
                dat[k] = a;
                while(k > 0){
                    k /= 2;
                    dat[k] = min(dat[k * 2], dat[k * 2 + 1]);
                }
            }
            void init(vector<ll> &v){
        	    for(int i = 0; i < v.size(); ++i) dat[i + n] = v[i];
        	    for(int i = n - 1; i >= 1; --i) {
        	        dat[i] = min(dat[i * 2], dat[i * 2 + 1]);
        	    }
        	}
            ll Q(ll a, ll b){
        	    return query(a, b, 1, 0, n);
        	}
            ll query(ll a, ll b, ll k, ll l, ll r){
                if(r <= a || b <= l) return dflt;
                if(a <= l && r <= b) return dat[k];
                ll vl = query(a, b, k * 2, l, (l + r) / 2);
                ll vr = query(a, b, k * 2 + 1, (l + r) / 2, r);
                return min(vl, vr);
            }
    };
    cin>>N;
    vec po(N, INF), pe(N, INF), inv(N), ans(0);
    rep(i,N){
        cin>>A;
        --A;
        (!(i&1) ? po[i] : pe[i]) = A;
        inv[A] = i;
    }
    SEGTREE odd(N, INF), even(N, INF);
    odd.init(po);
    even.init(pe);
    set<P> sec;
    sec.emplace(0, N);
    priority_queue<ll, vector<ll>, greater<ll> > pque;
    pque.push(odd.Q(0, N));
    while(ans.size() < N){
        int l = pque.top(), lid = inv[l];
        pque.pop();
        auto ite = sec.lower_bound(P(lid, INF));
        --ite;
        bool rev = (ite->fi)&1;
        if(rev ^ (lid&1)) cout<<"error1"<<endl;
        ans.push_back(l);
        (rev ? even : odd).update(lid, INF);
        int r = (rev ? odd : even).Q(lid, ite->se), rid = inv[r];
        if(rev ^ ((rid + 1) & 1)) {
            cout<<"error"<<' '<<rev<<endl;
            cout<<ite->fi<<' '<<ite->se<<endl;
        }
        ans.push_back(r);
        (rev ? odd : even).update(rid, INF);
        
        if(lid - ite->fi > 0){
            sec.insert(P(ite->fi, lid));
            pque.push((rev ? even : odd).Q(ite->fi, lid));
        }
        if(rid - lid > 2){
            rev = (lid + 1)&1;
            sec.insert(P(lid + 1, rid));
            pque.push((rev ? even : odd).Q(lid + 1, rid));
        }
        if(ite->se - (rid + 1)> 0){
            rev = (rid + 1)&1;
            sec.insert(P(rid + 1, ite->se));
            pque.push((rev ? even : odd).Q(rid + 1, ite->se));
        }
        sec.erase(ite);
    }
    rep(i,N) {
        cout<<ans[i] + 1;
        i < N - 1 ? cout<<' ' : cout<<endl;
    }
}

Measured memory_bytes: 23144