#include<bits/stdc++.h>
using namespace std;
long arr[50010],sum[50010][18],bst[50010][18],lt[50010][18],rt[50010][18];
int main(){
	long n;
	scanf("%ld",&n);
	for(int i=0;i<n;i++){
		scanf("%ld",&arr[i]);
	}
	for(int i=0;i<n;i++){
		sum[i][0]=arr[i];
		bst[i][0]=arr[i];
		lt[i][0]=arr[i];
		rt[i][0]=arr[i];
	}
	for(int i=0;i<n;i++){
		for(int j=1;i+(1<<(j))-1<n;j++){
			lt[i][j]=max(lt[i][j-1],sum[i][j-1]+lt[i+ 1<<(j-1) ][j-1]);
			rt[i][j]=max(rt[i][j-1]+sum[i+ 1<<(j-1)][j-1],rt[i+ 1<<(j-1)][j-1]);
			sum[i][j]=sum[i+ 1<<(j-1)][j-1]+sum[i][j-1];
			bst[i][j]=max(max(bst[i][j-1],bst[i+ 1<<(j-1)][j-1]),rt[i][j-1]+lt[i+ 1<<(j-1)][j-1]);
		}
	}
	long q,x,y,z;
	scanf("%ld",&q);
 
	while(q--){
		scanf("%ld %ld",&x,&y);
		//We can calculate the binary representation of (y-x) and calculate the answer
	}
	return 0;
}
 

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKbG9uZyBhcnJbNTAwMTBdLHN1bVs1MDAxMF1bMThdLGJzdFs1MDAxMF1bMThdLGx0WzUwMDEwXVsxOF0scnRbNTAwMTBdWzE4XTsKaW50IG1haW4oKXsKCWxvbmcgbjsKCXNjYW5mKCIlbGQiLCZuKTsKCWZvcihpbnQgaT0wO2k8bjtpKyspewoJCXNjYW5mKCIlbGQiLCZhcnJbaV0pOwoJfQoJZm9yKGludCBpPTA7aTxuO2krKyl7CgkJc3VtW2ldWzBdPWFycltpXTsKCQlic3RbaV1bMF09YXJyW2ldOwoJCWx0W2ldWzBdPWFycltpXTsKCQlydFtpXVswXT1hcnJbaV07Cgl9Cglmb3IoaW50IGk9MDtpPG47aSsrKXsKCQlmb3IoaW50IGo9MTtpKygxPDwoaikpLTE8bjtqKyspewoJCQlsdFtpXVtqXT1tYXgobHRbaV1bai0xXSxzdW1baV1bai0xXStsdFtpKyAxPDwoai0xKSBdW2otMV0pOwoJCQlydFtpXVtqXT1tYXgocnRbaV1bai0xXStzdW1baSsgMTw8KGotMSldW2otMV0scnRbaSsgMTw8KGotMSldW2otMV0pOwoJCQlzdW1baV1bal09c3VtW2krIDE8PChqLTEpXVtqLTFdK3N1bVtpXVtqLTFdOwoJCQlic3RbaV1bal09bWF4KG1heChic3RbaV1bai0xXSxic3RbaSsgMTw8KGotMSldW2otMV0pLHJ0W2ldW2otMV0rbHRbaSsgMTw8KGotMSldW2otMV0pOwoJCX0KCX0KCWxvbmcgcSx4LHksejsKCXNjYW5mKCIlbGQiLCZxKTsKCQoJd2hpbGUocS0tKXsKCQlzY2FuZigiJWxkICVsZCIsJngsJnkpOwoJCS8vV2UgY2FuIGNhbGN1bGF0ZSB0aGUgYmluYXJ5IHJlcHJlc2VudGF0aW9uIG9mICh5LXgpIGFuZCBjYWxjdWxhdGUgdGhlIGFuc3dlcgoJfQoJcmV0dXJuIDA7Cn0K