#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;
}