#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
mt19937 rnd(time(0));
int n,f[N],a[N],p[N],tr[N],w[N<<2],ct,V,T=500;
set<int>S;
bool cmp(int x,int y){
	return f[x]==f[y]?p[x]<p[y]:f[x]<f[y];
}
priority_queue<int,vector<int>,decltype(&cmp)>q(cmp);
#define L k<<1
#define R k<<1|1
void pushup(int k){
	w[k]=max(w[L],w[R]);
}
void build(int k,int l,int r){
	if(l==r)return w[k]=a[l],void();
	int mid=l+r>>1;
	build(L,l,mid),build(R,mid+1,r);
	pushup(k);
}
void query(int k,int l,int r,int x,int y,int &Mx){
	if(w[k]<=Mx)return;
	if(l==r){
		Mx=w[k],w[k]=0;
		q.push(l);
		S.insert(l);
		return;
	}
	int mid=l+r>>1;
	if(x<=mid)query(L,l,mid,x,y,Mx);
	if(y>mid)query(R,mid+1,r,x,y,Mx);
	pushup(k);
}
void Pop(int u){
	++ct;
	int l,r;
	S.erase(u);
	auto it=S.lower_bound(u);
	r=*it;
	--it;
	l=*it;
	query(1,1,n,l+1,r-1,V=a[l]);
}
vector<pair<int,int> >calc(){
	shuffle(p+1,p+n+1,rnd);
	vector<pair<int,int> >res;
	ct=V=0;
	build(1,1,n);
	query(1,1,n,1,n,V=0);
	while(ct<n){
		if(q.size()==3&&T%3==0){
			vector<int>tmp(3);
			tmp[0]=q.top(),q.pop();
			tmp[1]=q.top(),q.pop();
			tmp[2]=q.top(),q.pop();
			sort(tmp.begin(),tmp.end());
			if(f[tmp[0]]==f[tmp[2]]){
				q.push(tmp[0]);
				res.push_back(make_pair(a[tmp[1]],a[tmp[2]]));
				Pop(tmp[1]),Pop(tmp[2]);
				continue;
			}else{
				for(auto v:tmp)q.push(v);
			}
		}
		if(q.size()==1){
			int u=q.top();
			q.pop();
			Pop(u);
			res.push_back(make_pair(a[u],a[u]));
		}else{
			int u=q.top();
			q.pop();
			int v=q.top();
			q.pop();
			Pop(u),Pop(v);
			res.push_back(make_pair(a[u],a[v]));
		}
	}
	return res;
}
vector<pair<int, int> > min_shooting_buildings(vector<int> H){
	n=H.size();
	S.insert(0),S.insert(n+1);
	for(int i=n;i;--i){
		a[i]=H[i-1],p[i]=i;
		for(int j=a[i];j;j-=j&-j)f[i]=max(f[i],tr[j]);
		++f[i];
		for(int j=a[i];j<=n;j+=j&-j)tr[j]=max(tr[j],f[i]);
	}
	vector<pair<int,int> >ans=calc();if(n>10000)return ans;
	while(T--){
		vector<pair<int,int> >tmp=calc();
		if(tmp.size()<ans.size())ans=tmp;
	}
	return ans;
}