/*
*DIV 2 C.
*LINK:
*nilabja10201992
*/
#include <bits/stdc++.h>
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 m = l + (r-l)/2;
init(2*index,l,m);
init(2*index+1,m+1,r);
T[index].merge(T[2*index],T[2*index+1]);
}
}
void query(node& res, int l, int r, int u, int v, int index){
if(u==l && v==r){
res=T[index];
return;
}
else{
int m = l + (r-l)/2;
if(m>=v)
query(res,l,m,u,v,2*index);
else if(m<u)
query(res,m+1,r,u,v,2*index+1);
else{
node left,right;
query(left,l,m,u,m,2*index);
query(right,m+1,r,m+1,v,2*index+1);
res.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<<endl;
}
//cout<<"Execution time : "<<tick();
return 0;
}
LyoKKkRJViAyIEMuCipMSU5LOgoqbmlsYWJqYTEwMjAxOTkyCiovCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIE1BWCAxPDwxNgojZGVmaW5lIE1BWDIgTUFYPDwyCgppbnQgQVtNQVhdOwpzdHJ1Y3Qgbm9kZXsKICAgICAgaW50IGJlc3RsZWZ0c3VtLGJlc3RyaWdodHN1bSxzdW0sYmVzdHN1bTsKICAgICAgdm9pZCBtZXJnZShub2RlICZBLCBub2RlICZCKXsKICAgICAgICAgICAgc3VtID0gQS5zdW0gKyBCLnN1bTsKICAgICAgICAgICAgYmVzdGxlZnRzdW0gPSBtYXgoQS5iZXN0bGVmdHN1bSwgQS5zdW0gKyBCLmJlc3RsZWZ0c3VtKTsKICAgICAgICAgICAgYmVzdHJpZ2h0c3VtID0gbWF4KEEuYmVzdHJpZ2h0c3VtICsgQi5zdW0sIEIuYmVzdHJpZ2h0c3VtKTsKICAgICAgICAgICAgYmVzdHN1bSA9IG1heChtYXgoQS5iZXN0c3VtLEIuYmVzdHN1bSksQS5iZXN0cmlnaHRzdW0rQi5iZXN0bGVmdHN1bSk7CiAgICAgIH0KICAgICAgdm9pZCBjcmVhdGVMZWFmKGludCB2YWwpewogICAgICAgICAgICBzdW09YmVzdGxlZnRzdW09YmVzdHJpZ2h0c3VtPWJlc3RzdW09dmFsOwogICAgICB9Cn07Cgpub2RlIFRbTUFYMl07Cgp2b2lkIGluaXQoaW50IGluZGV4LCBpbnQgbCxpbnQgcil7CiAgICAgIGlmKGw9PXIpewogICAgICAgICAgICBUW2luZGV4XS5jcmVhdGVMZWFmKEFbbF0pOwogICAgICAgICAgICByZXR1cm47CiAgICAgIH0KICAgICAgZWxzZXsKICAgICAgICAgICAgaW50IG0gPSBsICsgKHItbCkvMjsKICAgICAgICAgICAgaW5pdCgyKmluZGV4LGwsbSk7CiAgICAgICAgICAgIGluaXQoMippbmRleCsxLG0rMSxyKTsKICAgICAgICAgICAgVFtpbmRleF0ubWVyZ2UoVFsyKmluZGV4XSxUWzIqaW5kZXgrMV0pOwogICAgICB9Cn0KCnZvaWQgcXVlcnkobm9kZSYgcmVzLCBpbnQgbCwgaW50IHIsIGludCB1LCBpbnQgdiwgaW50IGluZGV4KXsKICAgICAgaWYodT09bCAmJiB2PT1yKXsKICAgICAgICAgICAgcmVzPVRbaW5kZXhdOwogICAgICAgICAgICByZXR1cm47CiAgICAgIH0KICAgICAgZWxzZXsKICAgICAgICAgICAgaW50IG0gPSBsICsgKHItbCkvMjsKICAgICAgICAgICAgaWYobT49dikKICAgICAgICAgICAgICAgICAgcXVlcnkocmVzLGwsbSx1LHYsMippbmRleCk7CiAgICAgICAgICAgIGVsc2UgaWYobTx1KQogICAgICAgICAgICAgICAgICBxdWVyeShyZXMsbSsxLHIsdSx2LDIqaW5kZXgrMSk7CiAgICAgICAgICAgIGVsc2V7CiAgICAgICAgICAgICAgICAgIG5vZGUgbGVmdCxyaWdodDsKICAgICAgICAgICAgICAgICAgcXVlcnkobGVmdCxsLG0sdSxtLDIqaW5kZXgpOwogICAgICAgICAgICAgICAgICBxdWVyeShyaWdodCxtKzEscixtKzEsdiwyKmluZGV4KzEpOwogICAgICAgICAgICAgICAgICByZXMubWVyZ2UobGVmdCxyaWdodCk7CiAgICAgICAgICAgIH0KICAgICAgfQp9CmludCBtYWluKCkgewogICAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgICAgY2luLnRpZShOVUxMKTsKICAgICAgaW50IG4sdCx4LHk7CiAgICAgIGNpbj4+bjsKICAgICAgZm9yKGludCBpPTA7aTxuO2krKykKICAgICAgICAgICAgY2luPj5BW2ldOwogICAgICBpbml0KDEsMCxuLTEpOwogICAgICBjaW4+PnQ7CiAgICAgIG5vZGUgYW5zOwogICAgICB3aGlsZSh0LS0pewogICAgICAgICAgICBjaW4+Png+Pnk7CiAgICAgICAgICAgIHF1ZXJ5KGFucywwLG4tMSx4LTEseS0xLDEpOwogICAgICAgICAgICBjb3V0PDxhbnMuYmVzdHN1bTw8ZW5kbDsKICAgICAgfQoJLy9jb3V0PDwiRXhlY3V0aW9uIHRpbWUgOiAiPDx0aWNrKCk7CiAgICAgIHJldHVybiAwOwp9Cg==