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