#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cmath>

using namespace std;

void out() {
     cout.flush();
    int n;
    cin >> n;
    exit(0);
}

const int MX = 1000000;
const int INF = 1000000000;
int tree[2][MX], pos[2][MX];
int step, n;
vector<int> ans, a, prs, cs;
vector<pair<int, int> > ps;
vector<vector<int> > gr;

int findPosMin(int ind, int l, int r) {
    int p = -1;
    int val = INF;
    l += step;
    r += step;
    while (l <= r) {
          if (val > tree[ind][l]) {
              val = tree[ind][l];
              p = pos[ind][l];
          }
          if (val > tree[ind][r]) {
              val = tree[ind][r];
              p = pos[ind][r];
          }
          l = (l+1)/2;
          r = (r-1)/2;
    }
    return p;
}

int findPosMin(int l, int r) {
    int p0 = findPosMin(0, l, r);
    int p1 = findPosMin(1, l, r);
    return (a[p0] < a[p1]) ? p0 : p1;
}

int dfs(int l, int r) {
    //cout << "DFS " << l << ' ' << r << endl;
    if (l + 1 == r) {
        ps[a[l]] = make_pair(a[l], a[r]);
        cs[a[l]] = 0;
      //  cout << "DFS returns " << a[l] << endl;
        return a[l];
    }
    
    int p = findPosMin((l&1), l, r);
    if ((p - l)&1) {
        int pp = findPosMin((l&1), l, p-1);
        ps[a[pp]] = make_pair(a[pp], a[p]);
        if (pp > l) {
            prs[dfs(l, pp-1)] = a[pp];
            cs[a[pp]]++;
        }
        
        if (pp + 1 < p) {
            prs[dfs(pp+1, p-1)] = a[pp];
            cs[a[pp]]++;
        }
        
        if (p < r) {
            prs[dfs(p+1, r)] = a[pp];
            cs[a[pp]]++;        
        }
        //cout << "DFS returns " << a[pp] << endl;
        
        return a[pp];
    }
    else {
        int pp = findPosMin(1 - (p&1), p+1, r);
        ps[a[p]] = make_pair(a[p], a[pp]);
        if (p > l) {
            prs[dfs(l, p-1)] = a[p];
            cs[a[p]]++;
        }
        
        if (p + 1 < pp) {
            prs[dfs(p+1, pp-1)] = a[p];
            cs[a[p]]++;
        }
        
        if (pp < r) {
            prs[dfs(pp+1, r)] = a[p];
            cs[a[p]]++;
        }
       // cout << "DFS returns " << a[p] << endl;
        
        return a[p];
    }

}

void solve() {
     cin >> n;
     step = 1;
     while (step < n)
         step *= 2;
     a.assign(n, 0);
     ps.assign(n, make_pair(-1, -1));
     prs.assign(n, -1);
     cs.assign(n, 0);
     gr.assign(n, vector<int>());
     
     
     for (int i = 0; i < n; ++i) {
         cin >> a[i];
         --a[i];
         tree[i&1][step + i] = a[i];
         pos[i&1][step + i] = i;
         
         tree[(1 - (i&1))][step + i] = INF;
         pos[(1 - (i&1))][step + i] = i;
     }
     
     for (int ind = 0; ind <= 1; ++ind)
          for (int i = step - 1; i > 0; --i)
              if (tree[ind][2*i] < tree[ind][2*i+1]) {
                  tree[ind][i] = tree[ind][2*i];
                  pos[ind][i] = pos[ind][2*i];
              }
              else {
                  tree[ind][i] = tree[ind][2*i+1];
                  pos[ind][i] = pos[ind][2*i+1];
              }
              
     ans.clear();
     //cout << "DFS" << endl;
    
     int root = dfs(0, n-1);
     /*cout << "OK" << endl;
     for (int i = 0; i < n; ++i)
         cerr << prs[i] << ' ';
     cerr << endl;
     for (int i = 0; i < n; ++i)
         cerr << ps[i].first << ' ' << ps[i].second << "    ";
     cerr << endl;
     for (int i = 0; i < n; ++i)
         cerr << cs[i] << ' ';
     cerr << endl;
     */
     for (int i = 0; i < n; ++i)
         if (prs[i] >= 0)
            gr[prs[i]].push_back(i);
     
     set<pair<int, int> > ST;
     /*for (int i = 0; i < n; ++i)
         if (cs[i] == 0 && ps[i].first >= 0)
            ST.insert(ps[i]);*/
     ST.insert(ps[root]);
     //cerr << "EEE" << endl;
         set<pair<int, int> >::iterator it = ST.end();
     //cerr << ST.size() << " sz" << endl;
     while (!ST.empty()) {
         set<pair<int, int> >::iterator it = ST.begin();
       //  cerr << "EEE" << endl;
     
         //--it;
     //cerr << "EEE" << endl;
     
         pair<int, int> p = *it;
         //cerr << "EEE" << endl;
     
         ST.erase(it);
         //cerr << "EEE" << endl;
         ans.push_back(p.first);
         ans.push_back(p.second);
         //cerr << p.first << ' ' << p.second << " in ans" << endl;
         /*if (prs[p.first] < 0)
            break;
         if (--cs[prs[p.first]] == 0)
             ST.insert(ps[prs[p.first]]);*/
         for (int i = 0; i < (int)gr[p.first].size(); ++i)
             ST.insert(ps[gr[p.first][i]]);
     }
     
     for (int i = n-1; i >= 0; --i)
         cout << ans[n-1-i] + 1 << ' ';
     cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    out();
    return 0;
}


Measured memory_bytes: 34548