const   fin = 'sequencequery.in'; fout = 'sequencequery.out';

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

var     bufin, bufout : buffer;
        arb, first, last ,blast : arbore;
        sum ,best : vector;
        r : int64;
        finish ,x ,y : longword;

function max( a, b, c : int64 ) : int64;
begin
        if (b > a) then a := b;
        if (c > a) then a := c;
        max := a;
end;

procedure getmax( nod : longword );
var     st, dr, amb ,gmax : int64;
begin
        st := arb[nod * 2];
        dr := arb[nod * 2 + 1];
        amb := st + dr + sum[first[nod * 2 + 1] - 1] - sum[last[nod * 2]];
        gmax := max( st, dr, amb );
        if (gmax = amb) then
        begin
                arb[nod] := amb;
                first[nod] := first[nod * 2];
                last[nod] := last[nod * 2 + 1];
        end else
        if (gmax = dr) then
        begin
                arb[nod] := dr;
                first[nod] := first[nod * 2 + 1];
                last[nod] := last[nod * 2 + 1];
        end else
        begin
                arb[nod] := st;
                first[nod] := first[nod * 2];
                last[nod] := last[nod * 2];
        end;
end;

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

procedure getsol( nod : longword );
var     gmax : int64;
begin
        if (finish = 0) then
        begin
                r := arb[nod];
                finish := 1;
                best[1] := arb[nod];
                blast[1] := last[nod];
        end else
        begin
                finish := finish + 1;
                gmax := arb[nod] + best[finish - 1] + sum[first[nod] - 1] - sum[blast[finish - 1]];
                if (gmax >= arb[nod]) then
                begin
                        best[finish] := gmax;
                        blast[finish] := last[nod];
                end else
                begin
                        best[finish] := arb[nod];
                        blast[finish] := last[nod];
                end;
        end;
        if (best[finish] > r) then r := best[finish];
end;

procedure querry( nod, st, dr : longword );
var     mij : longword;
begin
        if (x <= st) and (dr <= y) then
        begin
                getsol( nod );
                exit();
        end;
        mij := (st + dr) div 2;
        if (x <= mij) then querry( nod * 2, st, mij );
        if (mij < y) then querry( nod * 2 + 1, mij + 1, dr );
end;

procedure main();
var     n, m, i : longword;
begin
        assign( input, fin ); reset( input );
        assign( output, fout ); rewrite( output );
        settextbuf( input, bufin );
        settextbuf( output, bufout );
        readln( n, m );
        for i := 1 to n do read( sum[i] );
        for i := 2 to n do sum[i] := sum[i] + sum[i - 1];

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

begin
        main();
end.