#include<bits/stdc++.h>
#define reg register
inline bool cmax(reg int &x,reg int y){return x<y?x=y,1:0;}
const int N=5e5+10;
int n,a[N],b[N],rk[N],g[N];
std::vector<int> vc[N];
struct BIT{
	int c[N];
	inline void mdf(reg int x,reg int k){for (;x<=n;x+=x&-x) cmax(c[x],k);}
	inline int qry(reg int x){reg int res=0;for (;x;x-=x&-x) cmax(res,c[x]); return res;}
}T;
namespace DS{
	int rt[N<<2],ls[N<<7],rs[N<<7],mx[N<<7],idx;
	void modify(reg int &o,reg int l,reg int r,reg int x,reg int k){
		if (!o) o=++idx; cmax(mx[o],k); if (l==r) return; reg int mid=l+r>>1;
		x<=mid?modify(ls[o],l,mid,x,k):modify(rs[o],mid+1,r,x,k);
	}
	void Modify(reg int o,reg int l,reg int r,reg int x,reg int y,reg int k){
		modify(rt[o],1,n,y,k); if (l==r) return; reg int mid=l+r>>1;
		x<=mid?Modify(o<<1,l,mid,x,y,k):Modify(o<<1|1,mid+1,r,x,y,k);
	}
	int query(reg int o,reg int l,reg int r,reg int L,reg int R){
		if (!o) return 0; if (L<=l&&r<=R) return mx[o]; reg int mid=l+r>>1,res=0;
		if (L<=mid) cmax(res,query(ls[o],l,mid,L,R)); if (R>mid) cmax(res,query(rs[o],mid+1,r,L,R)); return res;
	}
	int Query(reg int o,reg int l,reg int r,reg int L,reg int R,reg int p,reg int q){
		if (L<=l&&r<=R) return query(rt[o],1,n,p,q); reg int mid=l+r>>1,res=0;
		if (L<=mid) cmax(res,Query(o<<1,l,mid,L,R,p,q)); if (R>mid) cmax(res,Query(o<<1|1,mid+1,r,L,R,p,q)); return res;
	}
}
struct Segment{
	std::pair<int,int> mx[N<<2];
	void modify(reg int o,reg int l,reg int r,reg int x,reg std::pair<int,int> k){
		if (l==r) return mx[o]=k,void(); reg int mid=l+r>>1;
		x<=mid?modify(o<<1,l,mid,x,k):modify(o<<1|1,mid+1,r,x,k); mx[o]=std::max(mx[o<<1],mx[o<<1|1]);
	}
	std::pair<int,int> query(reg int o,reg int l,reg int r,reg int L,reg int R){
		if (L<=l&&r<=R) return mx[o]; reg int mid=l+r>>1; reg std::pair<int,int> res={0,0};
		if (L<=mid) res=std::max(res,query(o<<1,l,mid,L,R)); if (R>mid) res=std::max(res,query(o<<1|1,mid+1,r,L,R)); return res;
	}
}T2;
std::vector<std::pair<int,int>> min_shooting_buildings(std::vector<int> H){
	n=H.size(); for (reg int i=0;i<n;i++) g[a[i+1]=H[i]]=i+1; 
	for (reg int i=n;i;i--) vc[b[i]=T.qry(a[i])+1].push_back(i),T.mdf(a[i],b[i]);
	for (reg int i=1,cnt=0;i<=n;i++){
		std::sort(vc[i].begin(),vc[i].end(),[](reg int x,reg int y){
			if (x<y){if (a[x]>a[y]) return false; return DS::Query(1,1,n,x,y-1,1,a[x])<DS::Query(1,1,n,y,n,a[x]+1,a[y]);}
			else{if (a[x]<a[y]) return true; return DS::Query(1,1,n,x,n,a[y]+1,a[x])<DS::Query(1,1,n,y,x-1,1,a[y]);}
		});
		for (auto it:vc[i]) DS::Modify(1,1,n,it,a[it],rk[it]=++cnt);
	}
	std::priority_queue<std::pair<int,int>> pq;
	std::vector<std::pair<int,int>> ans;
	std::set<int> s;
	for (reg int i=1,pre=0;i<=n;i++){
		T2.modify(1,1,n,i,{a[i],i});
		if (pre<a[i]) pq.push({rk[i],i}),s.insert(a[i]),pre=a[i];
	}
	auto del=[&](reg int x)->void {
		s.erase(a[x]),T2.modify(1,1,n,x,{0,0});
		auto it=s.upper_bound(a[x]);
		reg int r=it==s.end()?n:g[*it]-1,mn=0;
		if (it!=s.begin()) mn=*--it;
		while (x<r){
			auto [v,p]=T2.query(1,1,n,x,r); if (v<=mn) break;
			s.insert(v),pq.push({rk[p],p}),r=p-1;
		}
	};
	while (!pq.empty()){
		auto [px,x]=pq.top(); pq.pop();
		// std::cerr<<x<<"\n";
		if (!pq.empty()){
			auto [py,y]=pq.top(); pq.pop();
			ans.push_back({a[x],a[y]}),del(y); 
		}else ans.push_back({a[x],a[x]}); del(x);
	}
	return ans;
}