Maximum Subarray Sum Queries

You are provided with an array of ‘N’ integers and ‘Q’ queries. Each query requires calculating the maximum subarray sum in a specified range of the array.

Input:

The first line contains ‘T’, representing the number of test cases. Each test case comprises the following: - The first line contains a single integer ‘N’ denoting the size of the ‘arr’ array. - The second line contains ‘N’ space-separated integers that represent the array ‘arr’. - The third line contains an integer ‘Q’ denoting the number of queries. - The next ‘Q’ lines in each test case contain two space-separated integers: ‘l’ and ‘r’, representing the range for which you must calculate the maximum subarray sum.

Output:

For each query per test case, output an integer denoting the maximum possible subarray sum in the range ‘l’ to ‘r’. Each test case should produce outputs on separate lines.

Example:

For a single test case, consider:

Input:
N = 5
arr = [-2, 1, -3, 4, -1]
Q = 2
Query 1: l = 0, r = 4
Query 2: l = 1, r = 3

Output:
4
2

Explanation: For the first query, the maximum subarray sum between indices 0 and 4 is 4 (subarray [4]). For the second query, the maximum subarray sum between indices 1 and 3 is 2 (subarray [1, -3, 4]).

Constraints:

• 1 ≤ T ≤ 5
• 1 ≤ N ≤ 10⁵
• 1 ≤ Q ≤ 10⁵
• -10⁹ ≤ arr[i] ≤ 10⁹

Ensure your solution meets the time limitation of 1 second.

Note:

Note that you do not need to print the output yourself. Implement the function as instructed and the results will be handled accordingly.