#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair
namespace{
    const ll MAXN = 1e5;
    ll n;
    ll a[MAXN+100];
    ll b[MAXN+100];
    ll rev[MAXN+100];
    vector <pair <int,int> > ans;
    void solve(){
        set <ll> s;
        for (ll i = 1;i <= n;i ++)s.insert(i);
        for (ll i = 1;i <= n;i ++){b[i] = n + 1 - a[i];rev[b[i]] = i;}
        ll inv[MAXN+100];
        while (sz(s)){
            vector <pll> tr;
            ll max1 = -1;
            for (auto x:s){
                if (a[x]>max1){
                    max1 = a[x];
                    ll max2 = max1;
                    for (auto y:s){
                        if (a[y] > max2){
                            max2 = a[y];
                            tr.push_back({x,y});
                        }
                    }
                }

            }
            pll best;
            ll cur_best = n+1;
            ll cur_best2 = -1;
            ll single=*s.begin();
            for (auto i:s){
                inv[i] = 0;
                for (auto j:s){
                    ll l = min(i,j),r = max(i,j);
                    if (a[l] > a[r])inv[i]++;
                }
            }
            for (auto x:tr){
                s.erase(x.fi);
                s.erase(x.se);
                vector <ll> lds;
                for (auto x:s){
                    auto tmp = upper_bound(lds.begin(),lds.end(),b[x]);
                    if (tmp==lds.end()){lds.push_back(b[x]);}
                    else (*tmp) = b[x];
                }
                ll sus = sz(lds);
                ll sus2 = inv[x.fi] + inv[x.se] - (a[x.fi] > a[x.se]);
//                cout<<sus<<' '<<x.fi<<' '<<x.se<<'\n';
                if (sus < cur_best || (sus==cur_best && sus2 > cur_best2)){
                    cur_best = sus;
                    cur_best2 = sus2;
                    best = x;
                }
                s.insert(x.fi);
                s.insert(x.se);
            }
            for (auto x:s){
                if (inv[x] > inv[single])single = x;
            }
            if (cur_best != n+1){
                s.erase(best.fi);
                s.erase(best.se);
                ans.push_back(MP(a[best.fi],a[best.se]));
            }
            else{
                s.erase(single);
                ans.push_back(MP(a[single],n+1));
            }
        }
//        sort(ans.begin(),ans.end());
    }
}
std::vector<std::pair<int, int>> min_shooting_buildings(std::vector<int> H){
    n = sz(H);
    for (ll i = 1;i <= n;i ++)a[i] = H[i-1];
	solve();
	return ans;
}