#include <iostream>
#include <cstring>
#include <cstdio> 
#include <algorithm>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
const int maxn=1000010;
int Max[maxn*4],a[maxn];
void Build(int rt,int l,int r){
	if(l==r){ Max[rt]=a[l]; return; }
	int mid=(l+r)>>1;
	Build(lson); Build(rson);
	Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
}
int QMax(int s,int t,int rt,int l,int r){
	if(s<=l&&t>=r) return Max[rt];
	int mid=(l+r)>>1;
	if(t<=mid) return QMax(s,t,lson);
	if(s>mid) return QMax(s,t,rson);
	return max(QMax(s,t,lson),QMax(s,t,rson));
}
int main(){
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	int n;scanf("%d",&n); n++;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	Build(1,1,n);
	int k;scanf("%d",&k);
	for(int i=1;i<=k;i++){
		int x,y;scanf("%d%d",&x,&y); x++; y++;
		printf("%d\n",QMax(x,y,1,1,n));	
	}
	return 0;
}