#include<cstdio>
using namespace std;
const int maxn =1e6 +100;
const int INF =10000;
FILE*fin,*fout;
int n,q,H[maxn];
int maxv[2*maxn],qL,qR;
inline int max(int a,int b){return a<b?b:a;}
void build(int o,int L,int R)
	{
	if(L == R){
		maxv[o] =H[L];
		return ;
	}
	else{
		int M =L +(R-L)/2;
		build(o*2,L,M);
		build(o*2+1,M+1,R);
		maxv[o]=max(maxv[o*2],maxv[o*2+1]);
	}}
	int query(int o,int L,int R)
	{
		if(R<qL||L>qR)return 0;
		int ans =0,M =L +(R-L)/2;
		if(L>=qL&&R<=qR)return maxv[o];
		if(M>=qL)ans =max(ans,query(o*2,L,M));
		if(M<qR)ans =max(ans,query(o*2+1,M+1,R));
		return ans;
	}
	int main()
	{
		freopen("climb.in","r",stdin);
		freopen("climb.out","w",stdout);
		scanf("%d",&n);
		for(int i =1;i <=n+1;i ++)scanf("%d",&H[i]);
		build(1,1,n+1);
		scanf("%d",&q);
		for(int i =1;i <=q;i++)
		{
			scanf("%d%d",&qL,&qR);
			qL++;qR++;
			printf("%d\n",query(1,1,n+1));
		}
	return 0;
    }