#include <bits/stdc++.h>
using namespace std;
long maxSubArraySum(long a[], long l, long r)
{
long max_so_far = INT_MIN, max_ending_here = 0;
for (long i = l; i <= r; i++)
{
max_ending_here = max_ending_here + a[i];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}
int main() {
// your code goes here
long m,n;
cin>>n;
long a[n];
for(long i=0;i<n;i++) cin>>a[i];
cin>>m;
while(m--){
long l,r;
cin>>l>>r;
cout<<maxSubArraySum(a,l-1,r-1)<<endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmxvbmcgbWF4U3ViQXJyYXlTdW0obG9uZyBhW10sIGxvbmcgbCwgbG9uZyByKSAKeyAKICAgIGxvbmcgbWF4X3NvX2ZhciA9IElOVF9NSU4sIG1heF9lbmRpbmdfaGVyZSA9IDA7IAogIAogICAgZm9yIChsb25nIGkgPSBsOyBpIDw9IHI7IGkrKykgCiAgICB7IAogICAgICAgIG1heF9lbmRpbmdfaGVyZSA9IG1heF9lbmRpbmdfaGVyZSArIGFbaV07IAogICAgICAgIGlmIChtYXhfc29fZmFyIDwgbWF4X2VuZGluZ19oZXJlKSAKICAgICAgICAgICAgbWF4X3NvX2ZhciA9IG1heF9lbmRpbmdfaGVyZTsgCiAgCiAgICAgICAgaWYgKG1heF9lbmRpbmdfaGVyZSA8IDApIAogICAgICAgICAgICBtYXhfZW5kaW5nX2hlcmUgPSAwOyAKICAgIH0gCiAgICByZXR1cm4gbWF4X3NvX2ZhcjsgCn0KaW50IG1haW4oKSB7CgkvLyB5b3VyIGNvZGUgZ29lcyBoZXJlCglsb25nIG0sbjsKCWNpbj4+bjsKCWxvbmcgYVtuXTsKCWZvcihsb25nIGk9MDtpPG47aSsrKSBjaW4+PmFbaV07CgljaW4+Pm07Cgl3aGlsZShtLS0pewoJCWxvbmcgbCxyOwoJCWNpbj4+bD4+cjsKCQljb3V0PDxtYXhTdWJBcnJheVN1bShhLGwtMSxyLTEpPDxlbmRsOwoJfQoJcmV0dXJuIDA7Cn0=