#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn=1000100;
int n,m;
int a[maxn];
int maxx[maxn][20];
void RMQ()
{
	int d=log(n*1.0)/log(2.0);
	for(int i=1;i<=n;++i)
	{
		maxx[i][0]=a[i];
	}
	for(int j=1;j<=d;++j)
	{
		for(int i=0;i<=n;++i)
		{
			int k=1<<(j-1);
			if(i+k<=n) maxx[i][j]=max(maxx[i][j-1],maxx[i+k][j-1]);	
		}
	}
}
int getmax(int x,int y)
{
	int d=log((y-x+1)*1.0)/log(2.0);
	int k=1<<d;
	return max(maxx[x][d],maxx[y-k+1][d]);
}
int main()
{
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	scanf("%d",&n);
	//n=n+1;
	for(int i=0;i<=n;++i)
	{
		scanf("%d",&a[i]);
	}
	RMQ();
	scanf("%d",&m);
	for(int i=1;i<=m;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		int k=getmax(x,y);
		printf("%d\n",k);
	}
	return 0;
}