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     arb ,first ,last : arbore;
        bufin, bufout : buffer;
        sum : vector;
        n ,x ,y ,finish : longword;
        r : int64;

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

procedure setmax( 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
                first[nod] := first[nod * 2];
                last[nod] := last[nod * 2 + 1];
                arb[nod] := amb;
        end else
        if (gmax = dr) then
        begin
                first[nod] := first[nod * 2 + 1];
                last[nod] := last[nod * 2 + 1];
                arb[nod] := dr;
        end else
        if (gmax = st) then
        begin
                first[nod] := first[nod * 2];
                last[nod] := last[nod * 2];
                arb[nod] := st;
        end;
end;

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

procedure getsol( nod : longword );
var     gmax ,amb : int64 ;
begin
        if (finish = 0) then
        begin
                finish := last[nod];
                r := arb[nod];
        end else
        begin
                amb := r + arb[nod] + sum[first[nod - 1]] - sum[finish];
                gmax := max( r, arb[nod] ,amb );
                if (gmax = amb) then
                begin
                        finish := last[nod];
                        r := amb;
                end else
                if (gmax = arb[nod]) then
                begin
                        finish := last[nod];
                        r := arb[nod];
                end;
        end;
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     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 - 1] + sum[i];

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

begin
        main();
end.