#include <bits/stdc++.h>
#define Pair pair<int,int>
#define mp make_pair
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
using namespace std;
template <typename T>
inline T read(){
	T x=0;char ch=getchar();bool fl=false;
	while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
	while(isdigit(ch)){
		x=(x<<3)+(x<<1)+(ch^48);ch=getchar();
	}
	return fl?-x:x;
}
#define read() read<int>()
const int maxn = 1e5 + 10;
namespace Tree{
struct tree{
	int l,r;
	int mn,tag;
}t[maxn<<2];
inline void pushup(int p){
	t[p].mn=min(t[ls].mn,t[rs].mn);
}
inline void pushdown(int p){
	if(!t[p].tag)return ;
	t[ls].mn+=t[p].tag;t[rs].mn+=t[p].tag;
	t[ls].tag+=t[p].tag;t[rs].tag+=t[p].tag;
	t[p].tag=0;
}
void build(int p,int l,int r){
	t[p].l=l;t[p].r=r;
	if(l==r)return t[p].mn=l,void();
	build(ls,l,mid);build(rs,mid+1,r);
	pushup(p);
}
void update(int p,int x,int y,int val){
	int l=t[p].l,r=t[p].r;
	if(x>y)return ;
	if(x<=l && r<=y){
		t[p].mn+=val;t[p].tag+=val;return ;
	}
	pushdown(p);
	if(x<=mid)update(ls,x,y,val);
	if(y>mid)update(rs,x,y,val);
	pushup(p);
}
int query(int p,int x,int y){
	int l=t[p].l,r=t[p].r;
	if(t[p].mn>0)return -1;
	if(l==r)return l;
	pushdown(p);
	if(y>mid && !t[rs].mn){
		int res=query(rs,x,y);
		if(res!=-1)return res;
	}
	if(x<=mid && !t[ls].mn)return query(ls,x,y);
	return -1;
}
}using namespace Tree;
int n,m,a[maxn];
int stk1[maxn],stk2[maxn],top1,top2;
vector<Pair> pos[maxn];
multiset<Pair> s;
Pair ans[maxn];
int main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	m=read();
	for(int i=1;i<=m;i++){
		int l=read(),r=read();
		pos[r].emplace_back(l,i);
	}
	build(1,1,n);
	for(int i=1;i<=n;i++){
		int x,y;
		while(top1 && a[stk1[top1]]<a[i]){
			y=stk1[top1];top1--;
			x=stk1[top1]+1;
			update(1,x,y,-a[y]);
		}
		x=stk1[top1]+1;y=i;
		update(1,x,y,a[y]);
		stk1[++top1]=i;
		while(top2 && a[stk2[top2]]>a[i]){
			y=stk2[top2];top2--;
			x=stk2[top2]+1;
			update(1,x,y,a[y]);
		}
		x=stk2[top2]+1;y=i;
		update(1,x,y,-a[y]);
		stk2[++top2]=i;
		update(1,1,n,-1);
		for(auto x:pos[i])s.insert(x);
		while(s.size()){
			auto it=s.end();it--;
			int l=it->first,res=query(1,1,l);
			if(res==-1)break;
			s.erase(it);
			ans[it->second].first=res;
			ans[it->second].second=i;
		}
	}
	for(int i=1;i<=m;i++)printf("%d %d\n",ans[i].first,ans[i].second);
	return 0;
}