Maximum Subarray Sum on a Given Range

You are given an array of integers and q queries. Each query is represented by two integers \(l\) and \(r\). For each query, find the maximum sum of any subarray that starts exactly at index \(l\) (1-indexed) and ends at some index between \(l\) and \(r\) (inclusive).

Note:

• If the subarray has all negative values, the answer is the maximum (least negative) element in that segment.
• The query indices are 1-based.

Input / Output Format: The input is read from standard input and the output is printed to standard output. See the input and output descriptions below for details.

inputFormat

The first line contains a single integer \(n\) denoting the size of the array.

The second line contains \(n\) space-separated integers representing the array elements.

The third line contains a single integer \(q\) denoting the number of queries.

Each of the next \(q\) lines contains two space-separated integers \(l\) and \(r\) representing a query.

outputFormat

For each query, output a single line containing the maximum subarray sum for the specified range.

## sample

5
-1 2 3 -2 5
3
1 3
2 5
1 5

5
8
8

</p>