#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1000001*2;
int k=1,n,maxa[maxn],_max=0,v,u,q;
void jianshu(int o)
{
	int l=o*2,r=o*2+1;
	if(o<k){jianshu(l);jianshu(r);maxa[o]=max(maxa[l],maxa[r]);}
}
void query(int o,int l,int r)
{
	int m=l+(r-l)/2;
	if(v<=l&&r<=u)_max=max(_max,maxa[o]);
	else if(l>u||r<v)return;
	else{
	int lc=o*2,rc=o*2+1;
	if(v<=m)query(lc,l,m);
	if(u>m)query(rc,m+1,r);
	}
}
int main()
{
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	scanf("%d",&n);
	while(k<n+1)k*=2;
	for(int i=k;i<=k+n;i++)
	  scanf("%d",&maxa[i]);
	jianshu(1);
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
	  scanf("%d%d",&v,&u);
	  v++;u++;
	  query(1,1,k);
	  printf("%d\n",_max);
	  _max=0;
	}
	return 0;
}