#include <cstdio>
#include <algorithm>
using namespace std;

#define L rt<<1,l,mid
#define R rt<<1|1,mid+1,r

const int maxn=1000010;
int n,m;
int a[maxn<<2];

void Build(int rt,int l,int r){
	if(l == r){
		scanf("%d",&a[rt]);
		return;
	}
	int mid = (l+r)>>1;
	Build(L);Build(R);
	a[rt] = max(a[rt<<1],a[rt<<1|1]);
}

int Query(int s,int t,int rt,int l,int r){
	if(s <= l && t >= r) return a[rt];
	int mid = (l+r)>>1;
	if(t <= mid) return Query(s,t,L);
	else if(s > mid) return Query(s,t,R);
	return max(Query(s,t,L), Query(s,t,R));
}

int main(){
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	scanf("%d",&n);
	n++;
	Build(1,1,n);
	scanf("%d",&m);
	int l,r;
	while(m --){
		scanf("%d%d",&l,&r);
		int ans=Query(l+1,r+1,1,1,n);
		printf("%d\n",ans);
	}
}