#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=1e6+100;
const int inf=10000;
FILE*fin,*fout;
int n,q,H[maxn];
int maxv[2*maxn],qL,qR;
inline int max(int a,int b){return a<b?b:a;}
void update(int o,int p,int v,int L,int R){
	//A[P]=v;
	int M=L+(R-L)/2;
	if(L==R) maxv[o]=v;//叶节点，直接更新
	else{
		if(p<=M) update(o*2,p,v,L,M);
		else update(o*2+1,p,v,M+1,R);
		maxv[o]=max(maxv[o*2],maxv[o*2+1]);
	} 
}
void build(int o,int L,int R){
	if(L==R){
		maxv[o]=H[L];
		//fprintf(fout,"o=%d,L=%d,R=%d,maxv[%d]=%d\n",o,L,R,o,H[L]);
		return ;
	}
	else{
		int M=L+(R-L)/2;
		build(o*2,L,M);
		build(o*2+1,M+1,R);
		maxv[o]=max(maxv[o*2],maxv[o*2+1]);
	}
}
int query(int o,int L,int R){
	//fprintf(fout,qL=%d,qR=%d,o=%d,L=%d,R=%d\n",qL,qR,o,,L,R);
	if(R<qL||L>qR) return 0;
	int ans=0,M=L+(R-L)/2;
	if(L>=qL&&R<=qR) return maxv[o];
	if(M>=qL) ans=max(ans,query(o*2,L,M));
	if(M<qR) ans=max(ans,query(o*2+1,M+1,R));
	return ans;
}
int main(){
	fin=fopen("climb.in","r");
	fout=fopen("climb.out","w");
	//fout=stdout;
	fscanf(fin,"%d",&n);
	for(int i=1;i<=n+1;i++) fscanf(fin,"%d",&H[i]);
	build(1,1,n+1);
	fscanf(fin,"%d",&q);
	for(int i=1;i<=q;i++){
		fscanf(fin,"%d%d",&qL,&qR);
		qL++;qR++;
		fprintf(fout,"%d\n",query(1,1,n+1)); 
	}
	return 0;
}