#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int h[1000100],maxv[2000200],n,k,maxn;
void build(int o,int l,int r)
{
	if(l==r) maxv[o]=h[l];
	else
	{
		int lc=o*2;
		int rc=o*2+1;
		build(lc,l,l+(r-l)/2);
		build(rc,l+(r-l)/2+1,r);
		maxv[o]=max(maxv[lc],maxv[rc]);
	}
	return;
}
void query(int o,int l,int r,int l0,int r0)
{
	if(l>=l0&&r<=r0) maxn=max(maxv[o],maxn);
	else
	{
		int m=l+(r-l)/2;
		int lc=o*2;
		int rc=o*2+1;
		if(m>=l0) query(lc,l,m,l0,r0);
		if(m<r0)  query(rc,m+1,r,l0,r0);
	}
	return;
}
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",&h[i]);
	build(1,1,n+1);
	scanf("%d",&k);
	for(int i=1;i<=k;i++)
	{
		int a,b;
		maxn=-1;
		scanf("%d%d",&a,&b);
		query(1,1,n+1,a+1,b+1);
		printf("%d",maxn);
	}
	return 0;
 }