#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

#define md (l+r)/2

const int Dim = 100001, Inf = 0x3f3f3f3f;

int n, m, a, b, A[Dim];
long long ans, sum;
long long Max[4 * Dim], L[4 * Dim], R[4 * Dim] ,S[4 * Dim];

void Build(int x, int l, int r);
void Query(int x, int l, int r);

int main()
{

    fin >> n >> m;

    for ( int i = 1; i <= n; i++ )
        fin >> A[i];

    Build(1, 1, n);

    while ( m )
    {
        m--;
        fin >> a >> b;
        sum = ans = -Inf;
        Query(1, 1, n);
        fout << ans << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}

void Build(int x, int l, int r)
{
    if ( l == r )
    {
        S[x] = A[l];
        Max[x] = L[x] = R[x] = A[l];
        return;
    }

    Build(2 * x, l, md);
    Build(2 * x + 1, md + 1, r);

    S[x] = S[2 * x] + S[2 * x + 1];
    L[x] = max(L[2 * x], S[2 * x] + L[2 * x + 1]);
    R[x] = max(R[2 * x + 1], R[2 * x] + S[2 * x + 1]);


    Max[x] = max(Max[2 * x + 1], Max[2 * x]);
    Max[x] = max(Max[x], R[2 * x] + L[2 * x + 1]);
}


void Query(int x, int l, int r)
{

    if (a <= l && r <= b)
    {
		if ( sum < 0 )
        {
            sum = 0;
        }
		ans = max(ans, max(sum + L[x], Max[x]));

        sum = max(sum + S[x], R[x]);
	}
	else
    {
		if (  a <= md  )
            Query(2 * x, l, md);
        if ( b > md)
            Query(2 * x + 1, md + 1, r);
    }
}