Maximum Subarray Sum Query

You are given an integer array A of size N. You need to process Q queries. For each query, two integers L and R are provided, and you must compute the maximum subarray sum for the segment A[L...R]. A subarray is a contiguous sequence of elements within the array.

In mathematical terms, for a given query, you are to compute:

$$\max_{L \leq i \leq j \leq R} \sum_{k=i}^{j} A[k]$$

Note that if all numbers in the segment are negative, the result is the maximum (i.e. least negative) number in that segment.

This problem can be efficiently solved using a modified version of Kadane's algorithm.

inputFormat

The first line of input contains an integer N representing the number of elements in the array. The second line contains N space-separated integers, which are the elements of the array A. The third line contains an integer Q representing the number of queries. This is followed by Q lines, each containing two integers L and R (0-indexed), representing the starting and ending indices of the query.

outputFormat

For each query, output a single line containing the maximum subarray sum for the subarray A[L...R].## sample

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

4
4