__author__ = "Achut"
from math import log
class Node:
def __init__(self):
self.sum = -15000
self.max = -15000
self.maxR = -15000
self.maxL = -15000
def seg_init(node, b, e, A, M):
if node is 4:
print("the node is ",M[node].sum)
if b is e:
M[node].sum = M[node].max = M[node].maxR = M[node].maxL = A[b]
print(node, M[node].sum,A[b])
else:
seg_init(2 * node, b, (b + e) / 2, A, M)
seg_init(2 * node + 1, (b + e) / 2 + 1, e, A, M)
print("booo")
print node,M[2*node].sum,2*node,M[node].sum
M[node].sum = M[2*node].sum + M[2*node + 1].sum
M[node].max = max(M[2*node].max,M[2*node +1].max,M[2*node].maxR+M[2*node+1].maxL)
M[node].maxR = max(M[node * 2 + 1].maxR, M[node * 2 + 1].sum + M[node * 2].maxR)
M[node].maxL = max(M[2*node + 1].maxL + M[2*node].sum , M[2*node].maxL)
print node,M[2*node].sum,2*node,M[node].sum
print("boooo over")
def query(node, b, e, A, M, i, j):
if b >= i and e <= j:
return M[node]
mid = (b + e) / 2
if j <= mid:
return query(2 * node, b,mid , A, M, i, j)
if i > mid:
return query(2 * node + 1, mid + 1, e, A, M, i, j)
p1 = query(2 * node, b,mid , A, M, i, j)
p2 = query(2 * node + 1, mid + 1, e, A, M, i, j)
result = Node()
result.sum = M[p1].sum + M[p2].sum
result.max = max(M[p1].max,M[p2].max,M[p1].maxR+M[p2].maxL)
result.maxR = max(M[p2].maxR, M[p2].sum + M[p1].maxR)
result.maxL = max(M[p2].maxL + M[p1].sum , M[p1].maxL)
return result
n = int(raw_input().strip())
M = [Node()] * (4 * 50005)
#print("length",len(M))
A = map(int, raw_input().strip().split())
print A
seg_init(1, 0, n - 1, A, M)
#for item in M:
# print item.sum
t = int(raw_input().strip())
while t:
t = t - 1
i, j = map(int, raw_input().strip().split())
print query(1, 0, n - 1, A, M, i - 1, j - 1).max
X19hdXRob3JfXyA9ICJBY2h1dCIKCmZyb20gbWF0aCBpbXBvcnQgbG9nCgoKY2xhc3MgTm9kZToKICAgIGRlZiBfX2luaXRfXyhzZWxmKToKICAgICAgICBzZWxmLnN1bSA9IC0xNTAwMAogICAgICAgIHNlbGYubWF4ID0gLTE1MDAwCiAgICAgICAgc2VsZi5tYXhSID0gLTE1MDAwCiAgICAgICAgc2VsZi5tYXhMID0gLTE1MDAwCgoKZGVmIHNlZ19pbml0KG5vZGUsIGIsIGUsIEEsIE0pOgogICAgaWYgbm9kZSBpcyA0OgogICAgICAgIHByaW50KCJ0aGUgbm9kZSBpcyAiLE1bbm9kZV0uc3VtKQogICAgaWYgYiBpcyBlOgogICAgICAgIE1bbm9kZV0uc3VtID0gTVtub2RlXS5tYXggPSBNW25vZGVdLm1heFIgPSBNW25vZGVdLm1heEwgPSBBW2JdCiAgICAgICAgcHJpbnQobm9kZSwgTVtub2RlXS5zdW0sQVtiXSkKICAgIGVsc2U6CiAgICAgICAgc2VnX2luaXQoMiAqIG5vZGUsIGIsIChiICsgZSkgLyAyLCBBLCBNKQogICAgICAgIHNlZ19pbml0KDIgKiBub2RlICsgMSwgKGIgKyBlKSAvIDIgKyAxLCBlLCBBLCBNKQogICAgICAgIHByaW50KCJib29vIikKICAgICAgICBwcmludCBub2RlLE1bMipub2RlXS5zdW0sMipub2RlLE1bbm9kZV0uc3VtCiAgICAgICAgTVtub2RlXS5zdW0gPSBNWzIqbm9kZV0uc3VtICsgTVsyKm5vZGUgKyAxXS5zdW0KICAgICAgICBNW25vZGVdLm1heCA9IG1heChNWzIqbm9kZV0ubWF4LE1bMipub2RlICsxXS5tYXgsTVsyKm5vZGVdLm1heFIrTVsyKm5vZGUrMV0ubWF4TCkKICAgICAgICBNW25vZGVdLm1heFIgPSBtYXgoTVtub2RlICogMiArIDFdLm1heFIsIE1bbm9kZSAqIDIgKyAxXS5zdW0gKyBNW25vZGUgKiAyXS5tYXhSKQogICAgICAgIE1bbm9kZV0ubWF4TCA9IG1heChNWzIqbm9kZSArIDFdLm1heEwgKyBNWzIqbm9kZV0uc3VtICwgTVsyKm5vZGVdLm1heEwpCiAgICAgICAgcHJpbnQgbm9kZSxNWzIqbm9kZV0uc3VtLDIqbm9kZSxNW25vZGVdLnN1bQogICAgICAgIHByaW50KCJib29vbyBvdmVyIikKCmRlZiBxdWVyeShub2RlLCBiLCBlLCBBLCBNLCBpLCBqKToKICAgIGlmIGIgPj0gaSBhbmQgZSA8PSBqOgogICAgICAgIHJldHVybiBNW25vZGVdCiAgICBtaWQgPSAoYiArIGUpIC8gMgogICAgaWYgaiA8PSBtaWQ6CiAgICAgICAgcmV0dXJuIHF1ZXJ5KDIgKiBub2RlLCBiLG1pZCAsIEEsIE0sIGksIGopCiAgICBpZiBpID4gbWlkOgogICAgICAgIHJldHVybiBxdWVyeSgyICogbm9kZSArIDEsIG1pZCArIDEsIGUsIEEsIE0sIGksIGopCgogICAgcDEgPSBxdWVyeSgyICogbm9kZSwgYixtaWQgLCBBLCBNLCBpLCBqKQogICAgcDIgPSBxdWVyeSgyICogbm9kZSArIDEsIG1pZCArIDEsIGUsIEEsIE0sIGksIGopCgogICAgcmVzdWx0ID0gTm9kZSgpCgogICAgcmVzdWx0LnN1bSA9IE1bcDFdLnN1bSArIE1bcDJdLnN1bQogICAgcmVzdWx0Lm1heCA9IG1heChNW3AxXS5tYXgsTVtwMl0ubWF4LE1bcDFdLm1heFIrTVtwMl0ubWF4TCkKICAgIHJlc3VsdC5tYXhSID0gbWF4KE1bcDJdLm1heFIsIE1bcDJdLnN1bSArIE1bcDFdLm1heFIpCiAgICByZXN1bHQubWF4TCA9IG1heChNW3AyXS5tYXhMICsgTVtwMV0uc3VtICwgTVtwMV0ubWF4TCkKCiAgICByZXR1cm4gcmVzdWx0CgpuID0gaW50KHJhd19pbnB1dCgpLnN0cmlwKCkpCk0gPSBbTm9kZSgpXSAqICg0ICogNTAwMDUpCiNwcmludCgibGVuZ3RoIixsZW4oTSkpCkEgPSBtYXAoaW50LCByYXdfaW5wdXQoKS5zdHJpcCgpLnNwbGl0KCkpCnByaW50IEEKCnNlZ19pbml0KDEsIDAsIG4gLSAxLCBBLCBNKQojZm9yIGl0ZW0gaW4gTToKIyAgICBwcmludCBpdGVtLnN1bQoKdCA9IGludChyYXdfaW5wdXQoKS5zdHJpcCgpKQoKd2hpbGUgdDoKICAgIHQgPSB0IC0gMQogICAgaSwgaiA9IG1hcChpbnQsIHJhd19pbnB1dCgpLnN0cmlwKCkuc3BsaXQoKSkKICAgIHByaW50IHF1ZXJ5KDEsIDAsIG4gLSAxLCBBLCBNLCBpIC0gMSwgaiAtIDEpLm1heAo=