#include <fstream>

using namespace std;

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

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

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

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

int n, m;

int x, y;

int sorin;

int aux;

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

void update ( int nod, int left, int right, int poz, int val)
{
    int 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 ( int nod, int left, int right )
{
    int 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 );
}