#include <fstream>

using namespace std;

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

void update ( long long nod, long long left, long long right, long long poz, long long val);

void f_find ( long long nod, long long left, long long right );

struct ura
{
    long long smax;
    long long s;
    long long sl;
    long long sr;
} aint[500137];

long long n, m;

long long x, y;

long long sorin;

long long aux;

int main()
{
    in >> n >> m;
    for ( register long long i = 1 ; i <= n ; ++i )
    {
        in >> x;
        update ( 1, 1, n, i, x );
    }
    for ( register long long j = 1 ; j <= m ; ++j )
    {
        in >> x >> y;
        sorin = -1e9;
        aux = 0;
        f_find ( 1, 1, n );
        out << sorin << '\n';
    }
    return 0;
}

void update ( long long nod, long long left, long long right, long long poz, long long val)
{
    long long mid = ( left + right ) / 2;
    if ( left == right )
    {
        aint[nod] = { val, val, val, val };
        return ;
    }
    if ( poz <= mid )
        update ( nod * 2, left, mid, poz, val );
    else
        update ( nod * 2 + 1, mid + 1, right, poz, val );
    aint[nod].s = aint[nod * 2].s + aint[nod * 2 + 1].s;
    aint[nod].smax = max ( aint[nod * 2].sr + aint[nod * 2 + 1].sl, max ( aint[nod * 2].smax, aint[nod * 2 + 1].smax ) );
    aint[nod].sl = max ( aint[nod * 2].sl, aint[nod * 2].s + aint[nod * 2 + 1].sl );
    aint[nod].sr = max ( aint[nod * 2 + 1].sr, aint[nod * 2 + 1].s + aint[nod * 2].sr );
}

void f_find ( long long nod, long long left, long long right )
{
    long long mid = ( left + right ) / 2;
    if ( x <= left && right <= y )
    {
        sorin = max ( sorin, max ( aint[nod].smax, aux + aint[nod].sl ) );
        aux = max ( aux + aint[nod].s, aint[nod].sr );
        return ;
    }
    if ( x <= mid )
        f_find ( nod * 2, left, mid );
    if ( mid < y )
        f_find ( nod * 2 + 1, mid + 1, right );
}