#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=1000000+10;
int n,q,maxn[MAXN],a[MAXN],Max,lo,ro;
void init()
{
	cin>>n;
	for(int i=1;i<=n+1;i++)
	 scanf("%d",&a[i]);
}
void build(int o,int l,int r){
	if(l==r)maxn[o]=a[l];
	else {
		int lc=o*2,rc=o*2+1;
		build(lc,l,l+(r-l)/2);
		build(rc,l+(r-l)/2+1,r);
		maxn[o]=max(maxn[lc],maxn[rc]);
//		cout<<maxn[o]<<"A";
	}
//	cout<<"A";
}
void man(int o,int l,int r){
	if(r < lo || l > ro)Max=0;;
	if(l>=lo&&r<=ro)Max=max(maxn[o],Max);
	else{
		int m=l+(r-l)/2;
	    int lc=o*2,rc=o*2+1;
	    if(m>=lo)man(lc,l,m);
	    if(m<ro)man(rc,m+1,r);
	}
	
	
}
int main()
{
	freopen("climb.in","r",stdin);freopen("climb.out","w",stdout);
	init();
	build(1,1,n+1);
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	 {
	 	scanf("%d%d",&lo,&ro);
		Max=0;
		lo++;ro++;
	 	man(1,1,n+1);
	 	printf("%d\n",Max);
	 }
	return 0;
}