Maximum Amusement

You are given a sequence of rides in an amusement park, each having an amusement rating (which may be negative). For a given query range \(l\) to \(r\), you are to determine the maximum possible contiguous subarray sum of the ratings in that range. In other words, for the subarray \(a[l], a[l+1], \ldots, a[r]\), find the maximum sum of any contiguous segment.

This can be mathematically represented as:

[ \text{result} = \max_{l \le i \le j \le r} \sum_{k=i}^{j} a[k] ]

It is guaranteed that there is at least one ride in each query's range. Your solution must correctly handle cases where all ratings are negative.

inputFormat

The first line contains two integers (n) and (q) separated by a space, denoting the number of rides and the number of queries respectively. (n) is the number of amusement rides and (q) is the number of queries.

The second line contains (n) integers, representing the amusement ratings of the rides.

Each of the next (q) lines contains two integers (l) and (r) (1-indexed), representing the starting and ending ride indices for the query.

outputFormat

For each query, output a single integer on a new line which represents the maximum contiguous subarray sum for that query's subarray.## sample

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

6
6
7