Maximum Subarray Sum for Subranges

The problem asks you to compute the maximum subarray sum for a specified subrange of an array using an efficient algorithm. Given an array of integers and a set of queries, where each query provides indices ( l ) and ( r ) (0-indexed), your task is to determine the largest sum that can be obtained by taking a contiguous subsequence from the subarray ( arr[l..r] ).

For example, consider the array [1, -2, 3, 4, -5] with a query (1, 3). The optimal subarray is [3, 4] which sums to 7. Use Kadane's algorithm to achieve an efficient solution.

inputFormat

The first line contains two integers ( n ) (the number of elements) and ( q ) (the number of queries).
The second line contains ( n ) integers separated by spaces representing the elements of the array.
Each of the following ( q ) lines contains two integers ( l ) and ( r ) detailing a query for the subarray ( arr[l..r] ).

outputFormat

For each query, output the maximum subarray sum for the subarray ( arr[l..r] ) on a new line.## sample

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

7
7
3