const   fin = 'sequencequery.in'; fout = 'sequencequery.out'; inf = -100001 * 100000;

type    buffer = array[0..1 shl 17] of char;
        arbore = array[0..1 shl 18] of int64;

var     bufin, bufout : buffer;
        first, last, sum, best : arbore;
        n ,x ,y : longword;
        r ,s : int64;

function max( a, b : int64 ) : int64;
begin
        if (a > b) then exit(a) else exit(b);
end;

procedure construct( nod, st, dr : longword );
var     mij : longword;
begin
        if (st = dr) then
        begin
                read( sum[nod] );
                first[nod] := sum[nod];
                last[nod] := sum[nod];
                best[nod] := sum[nod];
        end else
        begin
                mij := (st + dr) div 2;
                construct( nod * 2, st, mij );
                construct( nod * 2 + 1, mij + 1, dr );

                first[nod] := max( first[nod * 2], sum[nod * 2] + first[nod * 2 + 1] );
                last[nod] := max( last[nod * 2 + 1], sum[nod * 2 + 1] + last[nod * 2] );
                best[nod] := max( max( best[nod * 2], best[nod * 2 + 1] ), last[nod * 2] + first[nod * 2 + 1] );
                sum[nod] := sum[nod * 2] + sum[nod * 2 + 1];
        end;
end;

procedure query( nod, st, dr : longword );
var     mij : longword;
begin
        if (x <= st) and (dr <= y) then
        begin
                r := max( r, max( s + first[nod], best[nod] ) );
                s := max( s + sum[nod], last[nod] );
                exit();
        end;
                mij := (st + dr) div 2;
                if (x <= mij) then query( nod * 2, st, mij );
                if (mij < y) then query( nod * 2 + 1, mij + 1, dr);
end;

procedure main();
var     i, m : longword;
begin
        assign( input, fin ); reset( input );
        assign( output, fout ); rewrite( output );
        settextbuf( input, bufin );
        settextbuf( output, bufout );
        readln( n, m );

        construct( 1, 1, n );
        for i := 1 to m do
        begin
                read( x, y );
                r := inf;
                s := 0;
                query( 1, 1, n );
                write( r, #10 );
        end;
end;

begin
        main();
end.