#include<iostream>
#include<cstdio>
using namespace std;
int n,q;
int ql,qr;
const int maxn=1e6+10;
int ans[maxn*4],a[maxn];
void build(int p,int l,int r)
{
	if(l==r){
		ans[p]=a[l];return;
	}
	else {
		int m=(l+r)/2;
		build(2*p,l,m);
		build(2*p+1,m+1,r);
		ans[p]=max(ans[2*p],ans[2*p+1]);
	}
}
int query(int x,int y,int l,int r,int p)
{
	int res=0;
    if(x<=l&&r<=y)return ans[p];
    if(x<=(l+r)/2)res=max(res,query(x,y,l,(l+r)/2,2*p));
    if(y>(l+r)/2)res=max(res,query(x,y,(l+r)/2+1,r,2*p+1));
    return res;
}
int main()
{
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n+1;i++)
	{
		scanf("%d",&a[i]);
	}
	build(1,1,n+1);
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&ql,&qr);
		printf("%d\n",query(ql,qr,1,n,1));
	}
	fclose(stdin);fclose(stdout);
	return 0;
}