#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int maxsum[1000001][21];
void rmq(int n)//maxsum[i][j]表示i开始2的j次方个数据范围内的最大值；
{
	for(int j=1;j<=20;j++)
	{
		for(int i=1;i<=n;i++)
		{
			if(i+(1<<j)-1<=n)
			maxsum[i][j]=max(maxsum[i][j-1],maxsum[i+(1<<(j-1))][j-1]);//i+2的J-1次方！！！，第一次写错了！！！
		}
	}
}
int chaxun(int l,int r)//查询
{
	int k=0;
	while((1<<(k+1))<=r-l+1)k++;
	return max(maxsum[l][k],maxsum[r-(1<<k)+1][k]);
}
int main()
{
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	int n;
	cin>>n;
	n++;
	for(int i=1;i<=n;i++)
	{
		cin>>maxsum[i][0];
	}
	rmq(n);
	int m;
	cin>>m;
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		cout<<chaxun(x+1,y+1)<<endl;
	}
	return 0;
}