#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=100010;
struct tree
{
	int l,r;
	int max;
}a[2*maxn];
int c[maxn];
int maxx=-0x7fffffff;
int built(int k,int l,int r)
{
	a[k].l=l;
	a[k].r=r;
	if(l==r) a[k].max=c[l];
	else
	{
		built(2*k,l,(l+r)/2);
		built(2*k+1,(l+r)/2+1,r);
		a[k].max=max(a[2*k].max,a[2*k+1].max); 
	}
}
int query(int k,int l,int r)
{
	if(l<=a[k].l&&a[k].r<=r) maxx=max(maxx,a[k].max);
	else
	{
		if(l<=(a[k].l+a[k].r)/2)query(2*k,l,r);
		if(r>(a[k].l+a[k].r)/2)query(2*k+1,l,r);
	}
}
int n,m,x,y;
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",&c[i]);
	built(1,1,n+1);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		maxx=-0x7fffffff;
		query(1,x+1,y+1);
		printf("%d\n",maxx);
	}
	return 0;
}