Maximum Subarray Sum Within a Range

You are given an array \(a\) of \(n\) integers and \(q\) queries. For each query, represented by two integers \(l\) and \(r\) (1-indexed), you need to find the maximum sum of a contiguous subarray within the segment \(a[l...r]\). Note that if all numbers in the segment are negative, the answer is 0 (choosing an empty subarray).

The problem can be solved using a modification of Kadane's algorithm. Specifically, for a given segment \(a[l...r]\), you should compute the maximum subarray sum where the recurrence can be expressed in \(\text{LaTeX}\) as:

[ dp[i] = \max\left(a_i, dp[i-1] + a_i\right) \quad \text{for } i \ge 1, \quad \text{with } dp_0 = a_l ]

The answer for the query is \(\max(0, \max\limits_{l \le i \le r} dp[i])\). This ensures that if all numbers are negative, the maximum subarray sum taken is 0.

inputFormat

The first line of the input contains two integers \(n\) and \(q\) separated by a space, where \(n\) is the number of elements in the array and \(q\) is the number of queries.

The second line contains \(n\) integers representing the elements of the array \(a\), separated by spaces.

The following \(q\) lines each contain two integers \(l\) and \(r\) (1-indexed), representing the range for the query.

outputFormat

For each query, output the maximum subarray sum within the specified range on a new line.

## sample

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

6
4
4

</p>