#include<bits/stdc++.h>
using ll = int;
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];
    vector <pair <ll,ll> > ans;
    namespace seg{
        ll tree[MAXN*4+100];
        ll best(ll x,ll y){
            return (a[x] > a[y]) ? x : y;
        }
        void build(ll id = 1,ll l = 1,ll r = n){
            if (l == r){
                tree[id] = l;
                return;
            }
            else{
                ll mid = (l + r)>>1;
                build(id<<1,l,mid);
                build(id<<1|1,mid+1,r);
                tree[id] = best(tree[id<<1],tree[id<<1|1]);
            }
        }
        void update(ll i,ll id = 1,ll l = 1,ll r = n){
            if (i > r || i < l)return;
            if (l == r){
                tree[id] = 0;
                return;
            }
            ll mid = (l + r)>>1;
            update(i,id<<1,l,mid);
            update(i,id<<1|1,mid+1,r);
            tree[id] = best(tree[id<<1],tree[id<<1|1]);
        }
        ll get(ll i,ll id = 1,ll l = 1,ll r = n){
            if (i < l)return 0;
            if (r <= i)return tree[id];
            ll mid = (l + r) >> 1;
            return best(get(i,id<<1,l,mid),get(i,id<<1|1,mid+1,r));
        }
    }
    void solve(){
        seg::build();
        ll cnt = 0;
        while (cnt < n){
            ll max1 = seg::get(n);
            seg::update(max1);
            ll max2 = seg::get(max1);
            seg::update(max2);
            cnt += (max1 > 0) + (max2 > 0);
            pll tmp = MP(n+1,a[max1]);
            if (max2)tmp.fi = a[max2];
            ans.push_back(tmp);
        }
    }
}
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;
}