#include <fstream>
#include <climits>

using namespace std;

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

unsigned int x[100001], y[100001];
long long int sum;
unsigned int i, j;

long long int sol[100001];

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