#include<bits/stdc++.h>
 
int n,q;
int rmax[1000200][25],a[1000200];
 
inline int GetMax(const int& a, const int& b)
{
	return a>b?a:b;
}
 
int Read()
{
	int a=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')	ch=getchar();
	while(ch>='0'&&ch<='9'){
		a=a*10+ch-'0';
		ch=getchar();
	}
	return a;
}
 
void RmqInit()
{
	int m=log(n*1.0)/log(2.0);
	//换底公式,因为log(a)默认是以e为底a的对数
	//loga(b)=logc(b)/logc(a) 
	//log2(8)=ln(8)/ln(2) 
	for(int j=1;j<=m;j++){
		for(int i=1;i<=n;i++){
			rmax[i][j]=rmax[i][j-1];
			int k=1<<(j-1);	
			if(i+k<=n){
				rmax[i][j]=GetMax(rmax[i][j-1],rmax[i+k][j-1]);
				//类似动规 
			}	
		}
	}
}
 
inline int RmqMax(const int& s, const int& t)
{
	int m=log((t-s+1)*1.0)/log(2.0);
	int k=1<<m;
	return GetMax(rmax[s][m],rmax[t-k+1][m]);
	//中间可以有部分重复 
} 
 
void Init()
{
	n=Read();
	for(int i=1;i<=n+1;i++){
		a[i]=Read();
		rmax[i][0]=a[i];
		//rmax[i][j]:从i开始,长度为2的j次方的一段元素的最值 
	}
	RmqInit();
	q=Read();
	int s,t;
	for(int i=1;i<=q;i++){
		s=Read(),t=Read();
		printf("%d\n",RmqMax(s+1,t+1));
	}
}
 
int main()
{
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	Init();
	return 0;
}