#include <iostream>
#include <cstdio>
using namespace std;
const int MAX=int(1e6);
int read(){
	int x=0;
	char c=getchar();
	while(!(c>='0'&&c<='9'))
		c=getchar();
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
int maxx[MAX*4+10]={0};
int A[MAX+10];
void update(int o,int L,int R){
	int M=(L+R)>>1;
	if(L==R)
		maxx[o]=A[L];
	else {
		update(o*2,L,M);
		update(o*2+1,M+1,R);
		maxx[o]=max(maxx[o*2],maxx[o*2+1]);
	}
}
int ql,qr;
int query(int o,int L,int R){
	int M=(L+R)>>1;
	int ans=0;
	if(ql<=L&&R<=qr)
		return maxx[o];
	if(ql<=M)
		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(){
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	int n;
	n=read();
	for(int i=0;i<=n;i++)
		A[i]=read();
	update(1,0,n);
	int pq;
	pq=read();
	for(int i=1;i<=pq;i++){
		ql=read();
		qr=read();
		cout<<query(1,0,n)<<endl;
	}
return 0;
}