#include <bits/stdc++.h>
using namespace std;
#define MAXN 50001
class Data
{
public:
int sum, prefix, middle, suffix, best;
Data()
{
sum = prefix = middle = suffix = best = -15008;
}
};
int ar[MAXN];
Data tree[MAXN<<2];
class SegmentTree
{
int n;
void set(int node, int val)
{
tree[node].sum = tree[node].prefix = tree[node].middle = tree[node].suffix = tree[node].best = val;
}
void calc(int node, Data &d, Data &lChild, Data &rChild)
{
d.sum = lChild.sum + rChild.sum;
d.prefix = max(lChild.prefix, lChild.sum + rChild.prefix);
d.suffix = max(rChild.suffix, lChild.suffix + rChild.sum);
d.middle = lChild.suffix + rChild.prefix;
d.best = max({d.sum, d.prefix, d.middle, d.suffix, lChild.best, rChild.best});
}
void build(int s, int e, int node)
{
if(s==e) //leaf
set(node,ar[s]);
else
{
int m = s + (e-s)/2;
build(s,m,2*node);
build(m+1,e,2*node+1);
calc(node,tree[node],tree[2*node],tree[2*node+1]);
}
}
Data query(int l, int r, int s, int e, int node)
{
Data d;
if(s>r || e<l)
return d;
else if(s>=l && e<=r)
return tree[node];
int m = s+(e-s)/2;
if(l>m)
return query(l,r,m+1,e,2*node+1);
else if(r<=m)
return query(l,r,s,m,2*node);
else
{
Data lQuery = query(l,r,s,m,2*node);
Data rQuery = query(l,r,m+1,e,2*node+1);
calc(node,d,lQuery,rQuery);
return d;
}
}
public:
SegmentTree(int n)
{
this->n = n;
build(1,n,1);
}
int query(int l, int r)
{
return query(l,r,1,n,1).best;
}
};
int main()
{
int n; scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&ar[i]);
SegmentTree st(n);
int q; scanf("%d",&q);
while(q--)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",st.query(l,r));
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIE1BWE4gNTAwMDEKCmNsYXNzIERhdGEKewpwdWJsaWM6CglpbnQgc3VtLCBwcmVmaXgsIG1pZGRsZSwgc3VmZml4LCBiZXN0OwoJRGF0YSgpCgl7CgkJc3VtID0gcHJlZml4ID0gbWlkZGxlID0gc3VmZml4ID0gYmVzdCA9IC0xNTAwODsKCX0KfTsKCmludCBhcltNQVhOXTsKRGF0YSB0cmVlW01BWE48PDJdOwoKY2xhc3MgU2VnbWVudFRyZWUKewoJaW50IG47CgoJdm9pZCBzZXQoaW50IG5vZGUsIGludCB2YWwpCgl7CgkJdHJlZVtub2RlXS5zdW0gPSB0cmVlW25vZGVdLnByZWZpeCA9IHRyZWVbbm9kZV0ubWlkZGxlID0gdHJlZVtub2RlXS5zdWZmaXggPSB0cmVlW25vZGVdLmJlc3QgPSB2YWw7Cgl9CgoJdm9pZCBjYWxjKGludCBub2RlLCBEYXRhICZkLCBEYXRhICZsQ2hpbGQsIERhdGEgJnJDaGlsZCkKCXsKCQlkLnN1bSA9IGxDaGlsZC5zdW0gKyByQ2hpbGQuc3VtOwoJCWQucHJlZml4ID0gbWF4KGxDaGlsZC5wcmVmaXgsIGxDaGlsZC5zdW0gKyByQ2hpbGQucHJlZml4KTsKCQlkLnN1ZmZpeCA9IG1heChyQ2hpbGQuc3VmZml4LCBsQ2hpbGQuc3VmZml4ICsgckNoaWxkLnN1bSk7CgkJZC5taWRkbGUgPSBsQ2hpbGQuc3VmZml4ICsgckNoaWxkLnByZWZpeDsKCQlkLmJlc3QgPSBtYXgoe2Quc3VtLCBkLnByZWZpeCwgZC5taWRkbGUsIGQuc3VmZml4LCBsQ2hpbGQuYmVzdCwgckNoaWxkLmJlc3R9KTsKCX0KCgl2b2lkIGJ1aWxkKGludCBzLCBpbnQgZSwgaW50IG5vZGUpCgl7CgkJaWYocz09ZSkgLy9sZWFmCgkJCXNldChub2RlLGFyW3NdKTsKCQllbHNlCgkJewoJCQlpbnQgbSA9IHMgKyAoZS1zKS8yOwoJCQlidWlsZChzLG0sMipub2RlKTsKCQkJYnVpbGQobSsxLGUsMipub2RlKzEpOwoJCQljYWxjKG5vZGUsdHJlZVtub2RlXSx0cmVlWzIqbm9kZV0sdHJlZVsyKm5vZGUrMV0pOwoJCX0KCX0KCglEYXRhIHF1ZXJ5KGludCBsLCBpbnQgciwgaW50IHMsIGludCBlLCBpbnQgbm9kZSkKCXsKCQlEYXRhIGQ7CgkJaWYocz5yIHx8IGU8bCkKCQkJcmV0dXJuIGQ7CgkJZWxzZSBpZihzPj1sICYmIGU8PXIpCgkJCXJldHVybiB0cmVlW25vZGVdOwoKCQlpbnQgbSA9IHMrKGUtcykvMjsKCQlpZihsPm0pCgkJCXJldHVybiBxdWVyeShsLHIsbSsxLGUsMipub2RlKzEpOwoJCWVsc2UgaWYocjw9bSkKCQkJcmV0dXJuIHF1ZXJ5KGwscixzLG0sMipub2RlKTsKCQllbHNlCgkJewoJCQlEYXRhIGxRdWVyeSA9IHF1ZXJ5KGwscixzLG0sMipub2RlKTsKCQkJRGF0YSByUXVlcnkgPSBxdWVyeShsLHIsbSsxLGUsMipub2RlKzEpOwoJCQljYWxjKG5vZGUsZCxsUXVlcnksclF1ZXJ5KTsKCQkJcmV0dXJuIGQ7CgkJfQoJfQoKcHVibGljOgoJU2VnbWVudFRyZWUoaW50IG4pCgl7CgkJdGhpcy0+biA9IG47CgkJYnVpbGQoMSxuLDEpOwoJfQoKCWludCBxdWVyeShpbnQgbCwgaW50IHIpCgl7CgkJcmV0dXJuIHF1ZXJ5KGwsciwxLG4sMSkuYmVzdDsKCX0KCn07CgppbnQgbWFpbigpCnsKCWludCBuOyBzY2FuZigiJWQiLCZuKTsKCWZvcihpbnQgaT0xO2k8PW47aSsrKQoJCXNjYW5mKCIlZCIsJmFyW2ldKTsKCglTZWdtZW50VHJlZSBzdChuKTsKCWludCBxOyBzY2FuZigiJWQiLCZxKTsKCXdoaWxlKHEtLSkKCXsKCQlpbnQgbCxyOwoJCXNjYW5mKCIlZCVkIiwmbCwmcik7CgkJcHJpbnRmKCIlZFxuIixzdC5xdWVyeShsLHIpKTsKCX0KCXJldHVybiAwOwp9Cg==