'''
简单线段树应用
'''

from typing import List
import sys


class SegmentTree:
    class Node:
        def __init__(self, start, end):
            self.start = start      # 区段开始位置
            self.end = end          # 区段结束位置
            self.data = 0           # 区段中的信息
            self.left = None        # 左节点
            self.right = None       # 右节点

    # 更新单个数据
    def _update_single(self, root, idx, data):
        if root.start == root.end and root.start == idx:
            root.data += data
            return root.data

        else:
            mid = (root.start + root.end) // 2

            if idx <= mid:
                root.data = max(self._update_single(root.left, idx, data), root.right.data)
            else:
                root.data = max(root.left.data, self._update_single(root.right, idx, data))

            return root.data

    # 获取区间数据
    def _get_data(self, root, start, end):
        if root.start == start and root.end == end:
            # 节点刚好就表示[start, end]区间，不用分裂新节点
            return root.data

        else:
            mid = (root.start + root.end) // 2

            if end <= mid:
                return self._get_data(root.left, start, end)
            elif start >= mid + 1:
                return self._get_data(root.right, start, end)
            else:
                return max(self._get_data(root.left, start, mid), self._get_data(root.right, mid+1, end))


    def update_single(self, idx, data):
        self._update_single(self.root, idx, data)

    def get_data(self, start, end):
        return self._get_data(self.root, start, end)

    def __init__(self, n):
        self.__nodes = [self.Node(0, 0) for _ in range(4*n)]
        nodes = self.__nodes
        nodes[0].start, nodes[0].end = 0, n - 1
        self.root = self.__nodes[0]

        for i in range(4*n):
            if nodes[i].start == n-1 and nodes[i].end == n-1:
                break

            mid = (nodes[i].start + nodes[i].end) // 2
            nodes[i].left = nodes[2*i+1]
            nodes[i].left.start, nodes[i].left.end = nodes[i].start, mid

            nodes[i].right = nodes[2*i+2]
            nodes[i].right.start, nodes[i].right.end = mid+1, nodes[i].end

n = int(input())
tree = SegmentTree(n)
vals = list(map(int, input().split()))
for i, val in enumerate(vals):
    tree.update_single(i, val)

m = int(input())
for _ in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    print(tree.get_data(a, b))