Maximum Subarray Sum Queries

You are given an array and several queries. In each query, you are provided two integers \(l\) and \(r\) representing the range (1-indexed) on the array. Your task is to compute the maximum sum of any contiguous subarray within the subarray \(a[l \ldots r]\), using Kadane's algorithm.

The input may consist of multiple test cases. For each test case, the first line contains an integer \(n\) denoting the number of elements in the array, followed by \(n\) space-separated integers. Then an integer \(q\) specifies the number of queries. Each of the next \(q\) lines contains two integers \(l\) and \(r\).

For a given query, you can assume that \(1 \leq l \leq r \leq n\). The solution for each query should be computed independently and printed each on a new line.

Note: The Kadane's algorithm works by iteratively processing the array and keeping track of the maximum sum ending at the current index, and the overall maximum.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
n
a1 a2 ... an
q
l1 r1
l2 r2
...
lq rq

Where:

• T: Number of test case instances.
• For each test case:
• n: The number of elements in the array.
• a1, a2, ..., an: The array elements.
• q: The number of queries.
• Each query consists of two integers l and r.

outputFormat

For each query, output the maximum contiguous subarray sum within the specified range. The answers for the queries (across all test cases) should be printed on separate lines to standard output (stdout).

## sample

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

3
7

</p>