#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
const int maxn=1000050;
int ma[maxn<<2],n,m;
void Build(int,int,int);
int getmax(int,int,int,int,int);
int main()
{
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	scanf("%d",&n);n++;
	Build(1,1,n);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;scanf("%d%d",&x,&y);x++;y++;
		int ans=getmax(x,y,1,1,n);
		printf("%d\n",ans);
	}
	return 0;
}
void Build(int rt,int l,int r)
{
	if(l==r)
	{
		scanf("%d",&ma[rt]);
		return;
	}
	int mid=(l+r)>>1;
	Build(lson);
	Build(rson);
	ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
}
int getmax(int s,int t,int rt,int l,int r)
{
	if(s<=l&&t>=r)return ma[rt];
	int mid=(l+r)>>1;
	if(t<=mid)return getmax(s,t,lson);
	if(s>mid)return getmax(s,t,rson);
	return max(getmax(s,t,lson),getmax(s,t,rson));
}