#include <bits/stdc++.h>
typedef long long lld;
typedef unsigned long long llu;
#define rep(i,x,y) for(i=x;i<y;i++)
#define rrep(i,x,y) for(i=x;i>=y;i--)
#define trv(y,x) for(typeof(x.begin())y=x.begin();y!=x.end();y++)
#define MID(x,y) (x+((y-x)/2))
using namespace std;
#define MAX (1<<16)
#define MAX2 (MAX<<2)
int A[MAX];
struct node
{
int bestleftsum,bestrightsum,sum,bestsum;
void Merge(node &A,node &B)
{
sum=A.sum+B.sum;
bestleftsum=max(A.bestleftsum,A.sum+B.bestleftsum);
bestrightsum=max(A.bestrightsum+B.sum,B.bestrightsum);
bestsum=max(max(A.bestsum,B.bestsum),A.bestrightsum+B.bestleftsum);
}
void CreateLeaf(int val)
{
sum=bestleftsum=bestrightsum=bestsum=val;
}
};
node T[MAX2];
void init(int index,int l,int r)
{
if(l==r)
{
T[index].CreateLeaf(A[l]);
return;
}
else
{
int mid=MID(l,r);
init(2*index,l,mid);
init(2*index+1,mid+1,r);
T[index].Merge(T[2*index],T[2*index+1]);
}
}
void query(node& result,int l,int r,int u,int v,int index)
{
if(u==l && v==r)
{
result=T[index];
return;
}
else
{
int mid=MID(l,r);
if(mid>=v)
query(result,l,mid,u,v,2*index);
else if(mid<u)
query(result,mid+1,r,u,v,2*index+1);
else
{
node left,right;
query(left,l,mid,u,mid,2*index);
query(right,mid+1,r,mid+1,v,2*index+1);
result.Merge(left,right);
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,t,x,y;
cin>>n;
for(int i=0;i<n;i++)
cin>>A[i];
init(1,0,n-1);
cin>>t;
node Ans;
while(t--)
{
cin>>x>>y;
query(Ans,0,n-1,x-1,y-1,1);
cout<<Ans.bestsum<<"\n";
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiAKdHlwZWRlZiBsb25nIGxvbmcgbGxkOwp0eXBlZGVmIHVuc2lnbmVkIGxvbmcgbG9uZyBsbHU7CiNkZWZpbmUgcmVwKGkseCx5KSAgZm9yKGk9eDtpPHk7aSsrKQojZGVmaW5lIHJyZXAoaSx4LHkpIGZvcihpPXg7aT49eTtpLS0pCiNkZWZpbmUgdHJ2KHkseCkgICAgZm9yKHR5cGVvZih4LmJlZ2luKCkpeT14LmJlZ2luKCk7eSE9eC5lbmQoKTt5KyspCiNkZWZpbmUgTUlEKHgseSkgICAgKHgrKCh5LXgpLzIpKQp1c2luZyBuYW1lc3BhY2Ugc3RkOwogCiAKI2RlZmluZSBNQVggKDE8PDE2KQojZGVmaW5lIE1BWDIgKE1BWDw8MikKIAogCiAKIAppbnQgQVtNQVhdOwpzdHJ1Y3Qgbm9kZQp7CiAgICBpbnQgYmVzdGxlZnRzdW0sYmVzdHJpZ2h0c3VtLHN1bSxiZXN0c3VtOwogICAgdm9pZCBNZXJnZShub2RlICZBLG5vZGUgJkIpCiAgICB7CiAgICAgICAgc3VtPUEuc3VtK0Iuc3VtOwogICAgICAgIGJlc3RsZWZ0c3VtPW1heChBLmJlc3RsZWZ0c3VtLEEuc3VtK0IuYmVzdGxlZnRzdW0pOwogICAgICAgIGJlc3RyaWdodHN1bT1tYXgoQS5iZXN0cmlnaHRzdW0rQi5zdW0sQi5iZXN0cmlnaHRzdW0pOwogICAgICAgIGJlc3RzdW09bWF4KG1heChBLmJlc3RzdW0sQi5iZXN0c3VtKSxBLmJlc3RyaWdodHN1bStCLmJlc3RsZWZ0c3VtKTsKICAgIH0KICAgIHZvaWQgQ3JlYXRlTGVhZihpbnQgdmFsKQogICAgewogICAgICAgIHN1bT1iZXN0bGVmdHN1bT1iZXN0cmlnaHRzdW09YmVzdHN1bT12YWw7CiAgICB9Cn07CiAKIAogCiAgICBub2RlIFRbTUFYMl07CiAgICB2b2lkIGluaXQoaW50IGluZGV4LGludCBsLGludCByKQogICAgewogICAgICAgIGlmKGw9PXIpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIFRbaW5kZXhdLkNyZWF0ZUxlYWYoQVtsXSk7CiAgICAgICAgICAgICAgICByZXR1cm47CiAgICAgICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBpbnQgbWlkPU1JRChsLHIpOwogICAgICAgICAgICBpbml0KDIqaW5kZXgsbCxtaWQpOwogICAgICAgICAgICBpbml0KDIqaW5kZXgrMSxtaWQrMSxyKTsKICAgICAgICAgICAgVFtpbmRleF0uTWVyZ2UoVFsyKmluZGV4XSxUWzIqaW5kZXgrMV0pOwogICAgICAgIH0KIAogICAgfQogICAgdm9pZCBxdWVyeShub2RlJiByZXN1bHQsaW50IGwsaW50IHIsaW50IHUsaW50IHYsaW50IGluZGV4KQogICAgewogICAgICAgIGlmKHU9PWwgJiYgdj09cikKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgcmVzdWx0PVRbaW5kZXhdOwogICAgICAgICAgICAgICAgcmV0dXJuOwogICAgICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICBpbnQgbWlkPU1JRChsLHIpOwogICAgICAgICAgIGlmKG1pZD49dikKICAgICAgICAgICAgICAgIHF1ZXJ5KHJlc3VsdCxsLG1pZCx1LHYsMippbmRleCk7CiAgICAgICAgICAgIGVsc2UgaWYobWlkPHUpCiAgICAgICAgICAgICAgICBxdWVyeShyZXN1bHQsbWlkKzEscix1LHYsMippbmRleCsxKTsKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBub2RlIGxlZnQscmlnaHQ7CiAgICAgICAgICAgICAgICBxdWVyeShsZWZ0LGwsbWlkLHUsbWlkLDIqaW5kZXgpOwogICAgICAgICAgICAgICAgcXVlcnkocmlnaHQsbWlkKzEscixtaWQrMSx2LDIqaW5kZXgrMSk7CiAgICAgICAgICAgICAgICByZXN1bHQuTWVyZ2UobGVmdCxyaWdodCk7CiAgICAgICAgICAKICAgICAgICAgIAl9IAogICAgICAgICB9CiAgICB9IAoKaW50IG1haW4oKQp7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKCWNpbi50aWUoTlVMTCk7CiAgICBpbnQgbix0LHgseTsKICAgIGNpbj4+bjsKICAgIGZvcihpbnQgaT0wO2k8bjtpKyspCiAgICAgICAgY2luPj5BW2ldOwogICAgaW5pdCgxLDAsbi0xKTsKICAgIGNpbj4+dDsKICAgIG5vZGUgQW5zOwogICAgd2hpbGUodC0tKQogICAgewogICAgICAgIGNpbj4+eD4+eTsKICAgICAgICBxdWVyeShBbnMsMCxuLTEseC0xLHktMSwxKTsKICAgICAgICBjb3V0PDxBbnMuYmVzdHN1bTw8IlxuIjsKICAgIH0KIAogCiAKICAgIHJldHVybiAwOwp9