#include <fstream>
#include <vector>
using namespace std;

ifstream is("sequencequery.in");
ofstream os("sequencequery.out");

using VI = vector<int>;

int n, m, cnt;
int lt, rt, answ, sact;
VI nr, s, d, t, sum;

void Read();
void Build(int nod, int st, int dr);
void Query(int nod, int st, int dr);

int main()
{
    Read();
    Build(1, 1, n);
    while ( m-- )
    {
        is >> lt >> rt;
        answ = sact = -0x3f3f3f3f;
        Query(1, 1, n);
        os << answ << "\n";
    }
    is.close();
    os.close();
    return 0;
}

void Query(int nod, int st, int dr)
{
    if ( lt <= st && dr <= rt )
    {
        if ( sact < 0 )
            sact = 0;
        answ = max(answ, max(t[nod], sact + s[nod]));
        sact = max(sact + sum[nod], d[nod]);
        return;
    }
    int md = ( st + dr ) / 2;
    if ( lt <= md )
        Query(2 * nod, st, md);
    if ( rt > md )
        Query(2 * nod + 1, md + 1, dr);
}

void Read()
{
    is >> n >> m;
    nr = VI(n + 1);
    s = d = t = sum = VI(4 * n);
    for ( int i = 1; i <= n; ++i )
        is >> nr[i];
}

void Build(int nod, int st, int dr)
{
    if ( st == dr )
    {
        s[nod] = d[nod] = t[nod] = sum[nod] = nr[++cnt];
        return;
    }
    int md = ( st + dr ) / 2;
    Build(2 * nod, st, md);
    Build(2 * nod + 1, md + 1, dr);
    sum[nod] = sum[2 * nod] + sum[2 * nod + 1];
    s[nod] = max(s[2 * nod], sum[2 * nod] + s[2 * nod + 1]);
    d[nod] = max(d[2 * nod + 1], sum[2 * nod + 1] + d[2 * nod]);
    t[nod] = max(max(t[2 * nod], t[2 * nod + 1]), s[2 * nod + 1] + d[2 * nod]);
    t[nod] = max(t[nod], sum[nod]);
    t[nod] = max(t[nod], max(s[nod], d[nod]));
}