/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;

template<class T>
struct fenwick_tree_max{
    int n;
    vector<T> data;
    T T_id;
    fenwick_tree_max(int n, T init, T T_id = numeric_limits<T>::min()): fenwick_tree_max(vector<T>(n, init), T_id){ }
    fenwick_tree_max(const vector<T> &v, T T_id = numeric_limits<T>::min()): n((int)v.size()), data(v), T_id(T_id){
        for(auto i = 1; i <= n; ++ i) if(i + (i & -i) <= n) data[i + (i & -i) - 1] = max(data[i + (i & -i) - 1], data[i - 1]);
    }
    // O(log n)
    void update(int p, T x){
        assert(0 <= p && p < n);
        for(++ p; p <= n; p += p & -p) data[p - 1] = max(data[p - 1], x);
    }
    // O(log n)
    T pref(int r) const{
        T s = T_id;
        for(; r > 0; r -= r & -r) s = max(s, data[r - 1]);
        return s;
    }
    // pred(sum[0, r)) is T, T, ..., T, F, F, ..., F, returns max r with T
    // O(log n)
    int max_pref(auto pred) const{
        assert(pred(T_id));
        int p = 0;
        T pref = T_id;
        for(auto i = __lg(n + 1); i >= 0; -- i) if(p + (1 << i) <= n && pred(max(pref, data[p + (1 << i) - 1]))){
            pref = max(pref, data[p + (1 << i) - 1]);
            p += 1 << i;
        }
        return p;
    }
};

const int MAXT = 270000;

struct seg2
{
    pair<int, int> tree[MAXT];
    int lim;
    void init(int n)
    {
        fill(tree, tree + MAXT, pair<int, int>(-1e9, -1e9));
        for (lim = 1; lim <= n; lim <<= 1);
    }
    void upd(int x, pair<int, int> v)
    {
        x += lim;
        tree[x] = v;
        while (x > 1)
        {
            x >>= 1;
            tree[x] = max(tree[2 * x], tree[2 * x + 1]);
        }
    }
    pair<int, int> query(int s, int e)
    {
        s += lim;
        e += lim;
        pair<int, int> ret(-1e9, -1e9);
        while (s < e)
        {
            if (s % 2 == 1) ret = max(ret, tree[s++]);
            if (e % 2 == 0) ret = max(ret, tree[e--]);
            s >>= 1, e >>= 1;
        }
        if (s == e) ret = max(ret, tree[s]);
        return ret;
    }
} seg2;

vector<pair<int, int>> min_shooting_buildings(vector<int> a) {
    int n = isz(a);
    vector<int> dp(n);
    fenwick_tree_max<int> fenw(n, -1e9);
    vector<vector<int>> dpval, N(n);
    for (int i = n - 1; i >= 0; --i) {
        int val = max(0, fenw.pref(a[i]) + 1);
        dp[a[i] - 1] = val; fenw.update(a[i] - 1, val);
        if (val >= isz(dpval)) dpval.resize(val + 1);
        dpval[val].emplace_back(i);
    }

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (a[i] > a[j]) N[i].emplace_back(j);
        }
    }

    int cntt = 0;
    vector<int> rev = {-1};
    vector<int> ord(n);
    for (auto &v : dpval) {
        for (int val : v) {
            sort(all(N[val]), [&](int x, int y) {
                return ord[x] > ord[y];
            });
        }
        sort(all(v), [&](int x, int y) {
            for (int i = 0; i < min(isz(N[x]), isz(N[y])); ++i) if (N[x][i] != N[y][i]) {
                return (ord[N[x][i]] < ord[N[y][i]]);
            }
            if (isz(N[x]) != isz(N[y])) return isz(N[x]) < isz(N[y]);
            return (x > y);
        });
        for (int val : v) rev.push_back(val);
        for (int val : v) ord[val] = ++cntt;
    }

    
    vector<int> proc(n);
    iota(all(proc), 0);
    sort(all(proc), [&](int x, int y) { return ord[x] > ord[y]; });
    vector<pair<int, int>> ans;
    vector<int> killed(n);
    int cnt = 0;
    set<int> s, ord_s;
    {
        seg2.init(n);
        int curMax = -1;
        for (int j = 0; j < n; j++)
        {
            seg2.upd(j, pair<int, int>(a[j], j));
            if (curMax < a[j])
            {
                s.insert(j);
                ord_s.insert(ord[j]);
                curMax = a[j];
            }
        }
    }
    auto Erase = [&](int x)
    {
        auto nxt = s.upper_bound(x);
        int y = (nxt == s.end() ? n : *nxt);
        s.erase(x); ord_s.erase(ord[x]);
        seg2.upd(x, pair<int, int>(-1e9, x));
        while (y > 0)
        {
            auto val = seg2.query(0, y - 1);
            if (s.find(val.second) != s.end()) break;
            if (val.first < 0) break;
            s.insert(val.second);
            ord_s.insert(ord[val.second]);
            y = val.second;
        }
    };
    while (cnt < n)
    {
        if (isz(s) == 1)
        {
            cnt++;
            int nd = rev[*ord_s.begin()];
            Erase(nd);
            ans.emplace_back(a[nd], n);
        }
        else
        {
            cnt += 2;
            auto it = ord_s.end();
            int nd1 = rev[*--it];
            int nd2 = rev[*--it];
            Erase(nd1);
            Erase(nd2);
            ans.emplace_back(a[nd1], a[nd2]);
        }
    }
    return ans;
}