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