#include <fstream>
#include <climits>

using namespace std;

unsigned int N, M;
int a[100001];
unsigned int x, y;

int sum;
unsigned int i, j;

int maxSum;

int main ()
{
    ifstream fin ("sequencequery.in");
    fin >> N >> M;
    for (i=1; i<=N; i++)
        fin >> a[i];
    ofstream fout ("sequencequery.out");
    for (i=1; i<=M; i++)
    {
        fin >> x >> y;
        sum = 0;
        maxSum = INT_MIN;
        for (j=x; j<=y; j++)
        {
            if (sum < 0)
                sum = a[j];
            else
                sum += a[j];
            if (sum > maxSum)
                maxSum = sum;
        }
        fout << maxSum << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}