#include<cstdio>
#include<algorithm>
#define u tree[x]
#define lc tree[x<<1]
#define rc tree[x<<1|1]
using namespace std;
class poi{
public:
	int l,r;
	int max;
}tree[4000010];
int s[1000010],maxv;

void maketree(int x,int l,int r){
	u.l=l;
	u.r=r;
	if (l==r){
		u.max=s[l];
	}
	else{
		maketree(x<<1,l,l+r>>1);
		maketree(x<<1|1,(l+r>>1)+1,r);
		u.max=max(lc.max,rc.max);
	}
}

void query(int x,int l,int r){
	if (l<=u.l&&u.r<=r){
		maxv=max(u.max,maxv);
	}
	else{
		if (l<=lc.r)query(x<<1,l,r);
		if (r>=rc.l)query(x<<1|1,l,r);
	}
}

int main(){
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	int n;
	scanf("%d",&n);
	for (int i=0;i<=n;i++){
		scanf("%d",&s[i]);
	}
	maketree(1,0,n);
	int q;
	scanf("%d",&q);
	int l,r;
	for (int i=1;i<=q;i++){
		scanf("%d%d",&l,&r);
		maxv=0;
		query(1,l,r);
		printf("%d\n",maxv);
	}
	return 0;
}