#include<cstdio>
#include<cstring>
#define Cu fclose(stdin);fclose(stdout);return 0;
#define Begin freopen("climb.in","r",stdin);freopen("climb.out","w",stdout);chul();Cu;
//designed by New_Beeؼ 
using namespace std;
const int maxn=1000110;
int f[maxn<<4];int t=0,ans=0;
void chul();
int max(int,int);
void buildtree(int,int,int);
int find(int,int,int,int,int);
int main(){
	Begin; 
}
void chul(){
	int n;scanf("%d",&n);n++;
	buildtree(1,n,1);
	int m;scanf("%d",&m);
	for(int i=1;i<=m;i++){
		int s,t;
		scanf("%d%d",&s,&t);
		s++,t++;
		printf("%d\n",find(s,t,1,1,n));
	}
	
}
void buildtree(int s,int t,int rt){
	if(s==t){
		scanf("%d",&f[rt]);
		return;
	}
	int mid=(s+t)>>1;
	buildtree(s,mid,rt<<1);buildtree(mid+1,t,rt<<1|1);
	f[rt]=max(f[rt<<1],f[rt<<1|1]);
	return;
}
int find(int s,int t,int rt,int l,int r){
	if(s<=l&&t>=r){
		return f[rt];
	}
	int mid=(l+r)>>1;
	if(s>mid)return find(s,t,rt<<1|1,mid+1,r);
	if(t<=mid)return find(s,t,rt<<1,l,mid);
	return max(find(s,t,rt<<1|1,mid+1,r),find(s,t,rt<<1,l,mid));
}
int max(int x,int y){
	if(x>y)return x;
	return y;
}