runtime error (NZEC)

n = int(input())
a = [-1]+list(map(int, input().split(' ')))


class Node:
    def __init__(self, ans=0, l=0, r=0, _sum=0):
        self.a = ans
        self.l = l
        self.r = r
        self.s = _sum

    def __add__(self, other):
        res = Node()
        res.a = max(self.a, other.a, self.r+other.l)
        res.l = max(self.l, self.s+other.l)
        res.r = max(other.r, self.r+other.s)
        res.s = self.s + other.s
        return res

    def __radd__(self, other):
        res = Node()
        res.a = max(self.a, other.a, other.r+self.l)
        res.l = max(other.l, other.s+self.l)
        res.r = max(self.r, other.r+self.s)
        res.s = self.s + other.s
        return res

    def __repr__(self):
        return 'Node({ans=%d,l=%d,r=%d,_sum=%d})' % (self.a, self.l,
                                                     self.r, self.s)

    def init(self, val):
        if val > 0:
            self.l = self.r = self.a = self.s = val
        else:
            self.s = val

    def get_ans(self):
        return self.a


class SegmentTree:
    def __init__(self):
        self.ns = []
        for i in range(n << 2):
            self.ns.append(Node())

    def init(self, l, r, idx):
        if l == r:
            self.ns[idx].init(a[l])
        else:
            mid = (l+r) >> 1
            self.init(l, mid, idx << 1)
            self.init(mid+1, r, idx << 1 | 1)
            self.ns[idx] = self.ns[idx << 1]+self.ns[idx << 1 | 1]

    def debug(self):
        for i in self.ns:
            print(i)

    def ask(self, st, en, l, r, idx):
        if st <= l and r <= en:
            return self.ns[idx]
        mid = (l+r) >> 1
        if en <= mid:
            return self.ask(st, en, l, mid, idx << 1)
        if st > mid:
            return self.ask(st, en, mid+1, r, idx << 1 | 1)
        return self.ask(st, en, l, mid, idx << 1)+self.ask(st, en, mid+1, r,
                                                           idx << 1 | 1)


s = SegmentTree()
s.init(1, n, 1)
q = int(input())
for i in range(q):
    l, r = tuple(map(int, input().split(' ')))
    print(s.ask(l, r, 1, n, 1).get_ans())