#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;		
const int  maxn=1001000;
struct Node
{
	int  sum,l,r;
}a[maxn*4]={0};
void  Build(int ,int ,int );
void Init();
int  Qery(int ,int ,int );
int main()
{
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	Init();
}
void Init()
{
	int  n;
	scanf("%d",&n);
	Build(1,1,n+1);
	int  m;
	scanf("%d",&m);
	for(int  i=1;i<=m;i++)
	{
		int  s,t;
		scanf("%d%d",&s,&t);int  k=Qery(s+1,t+1,1);
		printf("%d\n",k);
	}
}
void  Build(int  rt,int  l,int  r)
{
	a[rt].l=l;
	a[rt].r=r;
	if(a[rt].l==a[rt].r)
	{
		scanf("%d",&a[rt].sum);
		return;
	}
	int  mid=(l+r)>>1;
	Build(rt<<1,l,mid);
	Build(rt<<1|1,mid+1,r);
	a[rt].sum=max(a[rt<<1].sum,a[rt<<1|1].sum);
}
int  Qery(int  s,int  t,int  rt)
{
	int  l=a[rt].l,r=a[rt].r;
	if(s<=l&&t>=r)return a[rt].sum;
	int  mid=(l+r)>>1;
	if(t<=mid) return Qery(s,t,rt<<1);
	if(s>mid)return Qery(s,t,rt<<1|1);
	else return max(Qery(s,t,rt<<1),Qery(s,t,rt<<1|1));
}