#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{int x,y;}ans[500005],tr[2000005];
int n,m,a[500005],sum[500005],l,r;
vector<pair<int,int> >v[500005];
bool operator <(node x,node y)
{
	if(x.y==0||y.y==0)return x.y==0;
	return x.x*y.y<x.y*y.x;
}
void cmax(node &x,node y){x=(x<y?y:x);}
int gcd(int x,int y){return (!y?x:gcd(y,x%y));}
void change(int k,int l,int r,int x,node v)
{
	if(l==r){cmax(tr[k],v);return;}
	int mid=(l+r)>>1;
	if(x<=mid)change(k<<1,l,mid,x,v);
	else change(k<<1|1,mid+1,r,x,v);
	tr[k]=tr[k<<1];cmax(tr[k],tr[k<<1|1]);
}
node query(int k,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)return tr[k];
	int mid=(l+r)>>1;node res={0,0};
	if(x<=mid)cmax(res,query(k<<1,l,mid,x,y));
	if(y>mid)cmax(res,query(k<<1|1,mid+1,r,x,y));
	return res;
}
signed main()
{
	//freopen("b.in","r",stdin);
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]+a[i];
	cin>>m;
	for(int i=1;i<=m;i++)cin>>l>>r,v[l].emplace_back(make_pair(r,i));
	for(int i=n;i>=1;i--)
	{
		if(a[i]==0)continue;
		node mx={0,0};
		for(int j=i;j<=n;j++)
		{
			if((sum[j]-sum[i-1]>0)!=(a[i]>0))break;
			node now={(sum[j]-sum[i-1])*(sum[j]-sum[i-1]),j-i+1};
			if(mx<now)mx=now,change(1,1,n,j,now);
			else assert(i!=j);
		}
		for(int j=0;j<v[i].size();j++)ans[v[i][j].second]=query(1,1,n,i,v[i][j].first);
	}
	return 0;
	for(int i=1;i<=m;i++)
	{
		int g=gcd(ans[i].x,ans[i].y);
		cout<<ans[i].x/g<<' '<<ans[i].y/g<<'\n';
	}
	return 0;
}