#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 200017 
#define ll long long
using namespace std;

int n;ll a[N],sum[N]; 

int binary_search(int l,int r){//找到第一个比 avg 大的 pos 
	ll avg = (sum[r]-sum[l-1])/2;
	int st = l-1,opt = -1;
	while(l <= r){
		int mid = (l+r)>>1;
		if(mid == opt)break;opt = mid;
		if(sum[mid]-sum[st] >= avg)r = mid;
		else l = mid+1;
	}
	if(sum[min(l,r)]-sum[st] >= avg)return min(l,r);
	else return max(l,r);
}

int main()
{
	cin >> n;
	for(int i = 1;i <= n;i += 1){
		cin >> a[i];
		sum[i] = sum[i-1] + a[i];
	}
	int q,l,r;cin >> q;
	for(int i = 1;i <= q;i += 1){
		cin >> l >> r;
		int p = binary_search(l,r);
		ll res = 0;
		if(p-1 >= l)res = max(res,(sum[p-1]-sum[l-1])*(sum[r]-sum[p-1]));
		if(p < r)res = max(res,(sum[p]-sum[l-1])*(sum[r]-sum[p]));
		cout << res << '\n';
	}
	return 0;
}