#include<stdio.h>
#include<map>
#define min -9999999
using namespace std;
struct node
{
long best, lsum, rsum, total;
};
map<long, node>segtree;
map<long, long>a;
long maxfun(long pg, long ss)
{
return pg>ss?pg:ss;
}
void pg(long pos)
{
segtree[pos].total = segtree[2*pos+1].total + segtree[2*pos+2].total;
segtree[pos].lsum = maxfun(segtree[2*pos + 1].lsum, segtree[2*pos + 1].total + segtree[2*pos+2].lsum);
segtree[pos].rsum = maxfun(segtree[2*pos + 2].rsum, segtree[2*pos + 2].total + segtree[2*pos+1].rsum);
segtree[pos].best = maxfun(maxfun(segtree[2*pos+1].best, segtree[2*pos+2].best), segtree[2*pos+1].rsum + segtree[2*pos+2].lsum);
}
void construct(long lo, long hi, long pos)
{
if(lo == hi)
{
segtree[pos].best = a[lo];
segtree[pos].lsum = a[lo];
segtree[pos].rsum = a[lo];
segtree[pos].total = a[lo];
return;
}
long mid = lo + (hi - lo)/2;
construct(lo, mid, 2*pos+1);
construct(mid+1, hi, 2*pos+2);
pg(pos);
}
node query(long qlo, long qhi, long lo, long hi, long pos)
{
if(qlo>hi || qhi<lo)
{
return (node) //MADE CHANGES HERE
{
min,
min,
min,
0
};//return something empty
}
if(qlo<=lo && qhi>=hi)
{
//res = segtree[pos].best;
return segtree[pos];
}
long mid = lo + (hi - lo)/2;
node left = query(qlo, qhi, lo, mid, 2*pos+1), right = query(qlo, qhi, mid+1, hi, 2*pos+2), pr;
pr.best = maxfun(maxfun(left.rsum+right.total, left.total + right.lsum),maxfun(left.best, right.best));
pr.lsum = maxfun(left.lsum, left.total + right.lsum);
pr.rsum = maxfun(left.rsum + right.total, right.rsum);
pr.total = left.total + right.total;
return pr;
}
int main()
{
//freopen("C:\\Users\\Shraeyas\\Documents\\pg\\pr_ag\\prag_gss1.txt", "r", stdin);
long n;
scanf("%ld", &n);
for(long i=0;i<n;i++)
{
scanf("%ld", &a[i]);
}
construct(0, n-1, 0);
long q;
scanf("%ld", &q);
while(q--)
{
long x,y;
scanf("%ld %ld", &x, &y);
x--, y--;
node pra = query(x, y, 0, n-1, 0);
printf("%ld\n", maxfun(maxfun(pra.lsum, pra.rsum), maxfun(pra.total, pra.best)));
}
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8bWFwPgoKI2RlZmluZSBtaW4gLTk5OTk5OTkKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3Qgbm9kZQp7Cglsb25nIGJlc3QsIGxzdW0sIHJzdW0sIHRvdGFsOwp9OwoKbWFwPGxvbmcsIG5vZGU+c2VndHJlZTsKbWFwPGxvbmcsIGxvbmc+YTsKCmxvbmcgbWF4ZnVuKGxvbmcgcGcsIGxvbmcgc3MpCnsKCXJldHVybiBwZz5zcz9wZzpzczsKfQoKdm9pZCBwZyhsb25nIHBvcykKewoJc2VndHJlZVtwb3NdLnRvdGFsID0gc2VndHJlZVsyKnBvcysxXS50b3RhbCArIHNlZ3RyZWVbMipwb3MrMl0udG90YWw7CglzZWd0cmVlW3Bvc10ubHN1bSA9IG1heGZ1bihzZWd0cmVlWzIqcG9zICsgMV0ubHN1bSwgc2VndHJlZVsyKnBvcyArIDFdLnRvdGFsICsgc2VndHJlZVsyKnBvcysyXS5sc3VtKTsKCXNlZ3RyZWVbcG9zXS5yc3VtID0gbWF4ZnVuKHNlZ3RyZWVbMipwb3MgKyAyXS5yc3VtLCBzZWd0cmVlWzIqcG9zICsgMl0udG90YWwgKyBzZWd0cmVlWzIqcG9zKzFdLnJzdW0pOwoJc2VndHJlZVtwb3NdLmJlc3QgPSBtYXhmdW4obWF4ZnVuKHNlZ3RyZWVbMipwb3MrMV0uYmVzdCwgc2VndHJlZVsyKnBvcysyXS5iZXN0KSwgc2VndHJlZVsyKnBvcysxXS5yc3VtICsgc2VndHJlZVsyKnBvcysyXS5sc3VtKTsKfQoKdm9pZCBjb25zdHJ1Y3QobG9uZyBsbywgbG9uZyBoaSwgbG9uZyBwb3MpCnsKCWlmKGxvID09IGhpKQoJewoJCXNlZ3RyZWVbcG9zXS5iZXN0ID0gYVtsb107CgkJc2VndHJlZVtwb3NdLmxzdW0gPSBhW2xvXTsKCQlzZWd0cmVlW3Bvc10ucnN1bSA9IGFbbG9dOwoJCXNlZ3RyZWVbcG9zXS50b3RhbCA9IGFbbG9dOwoJCQoJCXJldHVybjsKCX0KCQoJbG9uZyBtaWQgPSBsbyArIChoaSAtIGxvKS8yOwoJCgljb25zdHJ1Y3QobG8sIG1pZCwgMipwb3MrMSk7Cgljb25zdHJ1Y3QobWlkKzEsIGhpLCAyKnBvcysyKTsKCQoJcGcocG9zKTsKfQoKbm9kZSBxdWVyeShsb25nIHFsbywgbG9uZyBxaGksIGxvbmcgbG8sIGxvbmcgaGksIGxvbmcgcG9zKQp7CglpZihxbG8+aGkgfHwgcWhpPGxvKQoJewoJCXJldHVybiAobm9kZSkJCQkJLy9NQURFIENIQU5HRVMgSEVSRQoJCXsKCQkJbWluLCAKCQkJbWluLCAKCQkJbWluLCAKCQkJMAoJCX07Ly9yZXR1cm4gc29tZXRoaW5nIGVtcHR5Cgl9CgkKCWlmKHFsbzw9bG8gJiYgcWhpPj1oaSkKCXsKCQkvL3JlcyA9IHNlZ3RyZWVbcG9zXS5iZXN0OwoJCXJldHVybiBzZWd0cmVlW3Bvc107Cgl9CgkKCWxvbmcgbWlkID0gbG8gKyAoaGkgLSBsbykvMjsKCQoJbm9kZSBsZWZ0ID0gcXVlcnkocWxvLCBxaGksIGxvLCBtaWQsIDIqcG9zKzEpLCByaWdodCA9IHF1ZXJ5KHFsbywgcWhpLCBtaWQrMSwgaGksIDIqcG9zKzIpLCBwcjsKCQoJcHIuYmVzdCA9IG1heGZ1bihtYXhmdW4obGVmdC5yc3VtK3JpZ2h0LnRvdGFsLCBsZWZ0LnRvdGFsICsgcmlnaHQubHN1bSksbWF4ZnVuKGxlZnQuYmVzdCwgcmlnaHQuYmVzdCkpOwoJcHIubHN1bSA9IG1heGZ1bihsZWZ0LmxzdW0sIGxlZnQudG90YWwgKyByaWdodC5sc3VtKTsKCXByLnJzdW0gPSBtYXhmdW4obGVmdC5yc3VtICsgcmlnaHQudG90YWwsIHJpZ2h0LnJzdW0pOwoJcHIudG90YWwgPSBsZWZ0LnRvdGFsICsgcmlnaHQudG90YWw7CgkKCXJldHVybiBwcjsKCQp9CgoKaW50IG1haW4oKQp7CgoJLy9mcmVvcGVuKCJDOlxcVXNlcnNcXFNocmFleWFzXFxEb2N1bWVudHNcXHBnXFxwcl9hZ1xccHJhZ19nc3MxLnR4dCIsICJyIiwgc3RkaW4pOwoJCglsb25nIG47CglzY2FuZigiJWxkIiwgJm4pOwoJCglmb3IobG9uZyBpPTA7aTxuO2krKykKCXsKCQlzY2FuZigiJWxkIiwgJmFbaV0pOwoJfQoJCgljb25zdHJ1Y3QoMCwgbi0xLCAwKTsKCQkKCWxvbmcgcTsKCXNjYW5mKCIlbGQiLCAmcSk7CgkKCXdoaWxlKHEtLSkKCXsKCQlsb25nIHgseTsKCQlzY2FuZigiJWxkICVsZCIsICZ4LCAmeSk7CgkJeC0tLCB5LS07CgkJCgkJbm9kZSBwcmEgPSBxdWVyeSh4LCB5LCAwLCBuLTEsIDApOwoJCQoJCXByaW50ZigiJWxkXG4iLCBtYXhmdW4obWF4ZnVuKHByYS5sc3VtLCBwcmEucnN1bSksIG1heGZ1bihwcmEudG90YWwsIHByYS5iZXN0KSkpOwoJfQp9Cg==