#include<cstdio>
#include<algorithm>
using namespace std;
 
#define rmq 1,N,0
int data[500000*4];
int N,M,in;
 
void update(int id,int v,int L,int R,int i)
{
	if(L==R){
		data[i]=v;
		return;
	}
	int M=(L+R)/2;
	if(id<=M)update(id,v,L  ,M,i*2+1);
	else	 update(id,v,M+1,R,i*2+2);
	data[i]=max(data[i*2+1],data[i*2+2]);
}
int find(int l,int r,int L,int R,int i)
{
	if(L==l&&R==r)return data[i];
	int M=(L+R)/2;
	if(r<=M)return find(l,r,L  ,M,i*2+1);
	if(M< l)return find(l,r,M+1,R,i*2+2);
	return max(	find(l  ,M,L  ,M,i*2+1),
				find(M+1,r,M+1,R,i*2+2));
}
int main()
{
	int a,b;
	scanf("%d",&N);
	for(int i=1;i<=N;++i){
		scanf("%d",&in);
		update(i,in,rmq);
	}
	scanf("%d",&M);
	while(M--)
	{
		scanf("%d%d",&a,&b);
		if(a>b)swap(a,b);
		printf("%d\n",find(a,b,rmq));
	}
}

I2luY2x1ZGU8Y3N0ZGlvPgojaW5jbHVkZTxhbGdvcml0aG0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIHJtcSAxLE4sMAppbnQgZGF0YVs1MDAwMDAqNF07CmludCBOLE0saW47Cgp2b2lkIHVwZGF0ZShpbnQgaWQsaW50IHYsaW50IEwsaW50IFIsaW50IGkpCnsKCWlmKEw9PVIpewoJCWRhdGFbaV09djsKCQlyZXR1cm47Cgl9CglpbnQgTT0oTCtSKS8yOwoJaWYoaWQ8PU0pdXBkYXRlKGlkLHYsTCAgLE0saSoyKzEpOwoJZWxzZQkgdXBkYXRlKGlkLHYsTSsxLFIsaSoyKzIpOwoJZGF0YVtpXT1tYXgoZGF0YVtpKjIrMV0sZGF0YVtpKjIrMl0pOwp9CmludCBmaW5kKGludCBsLGludCByLGludCBMLGludCBSLGludCBpKQp7CglpZihMPT1sJiZSPT1yKXJldHVybiBkYXRhW2ldOwoJaW50IE09KEwrUikvMjsKCWlmKHI8PU0pcmV0dXJuIGZpbmQobCxyLEwgICxNLGkqMisxKTsKCWlmKE08IGwpcmV0dXJuIGZpbmQobCxyLE0rMSxSLGkqMisyKTsKCXJldHVybiBtYXgoCWZpbmQobCAgLE0sTCAgLE0saSoyKzEpLAoJCQkJZmluZChNKzEscixNKzEsUixpKjIrMikpOwp9CmludCBtYWluKCkKewoJaW50IGEsYjsKCXNjYW5mKCIlZCIsJk4pOwoJZm9yKGludCBpPTE7aTw9TjsrK2kpewoJCXNjYW5mKCIlZCIsJmluKTsKCQl1cGRhdGUoaSxpbixybXEpOwoJfQoJc2NhbmYoIiVkIiwmTSk7Cgl3aGlsZShNLS0pCgl7CgkJc2NhbmYoIiVkJWQiLCZhLCZiKTsKCQlpZihhPmIpc3dhcChhLGIpOwoJCXByaW50ZigiJWRcbiIsZmluZChhLGIscm1xKSk7Cgl9Cn0=