//infoarena sequence query
//arbori de intervale - > O(log n ) / query
const nmax = 110005;

var n,m,a,b:longint;
    sir : array[1..nmax] of longint;
    aa,bb,c,sum:array[1..2*nmax] of int64;
    s,ans: int64;

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

procedure build(n,l,r:longint);
begin

if  l = r then
        begin
        aa[n]:=sir[l];
        bb[n]:=aa[n];
        c[n]:=aa[n];
        sum[n]:=sir[l];
        end
else
        begin
        build(2*n,l,(l+r) div 2);
        build(2*n+1, ((l+r) div 2) + 1, r);

        aa[n]:=max(aa[2*n], sum[2*n] + aa[2*n+1]);
        bb[n]:=max(bb[2*n] + sum[2*n+1], bb[2*n+1]);
        c[n]:= max(max(c[2*n], c[2*n+1]), bb[2*n] + aa[2*n+1]);
        sum[n]:=sum[2*n]+sum[2*n+1];
        end;
end;

procedure query(n,l,r:longint);
begin
if ( a<= l) and ( r<=b) then
        begin
        //if (s < 0) then s:=0;
        ans:=max(ans,max(s+aa[n],c[n]));
        s:=max(s+sum[n], bb[n]);
        end
else
        begin
        if (a <= (l+r) div 2 ) then query(2*n, l,(l+r) div 2);
        if (b > (l+r) div 2) then query(2*n+1, ( (l+r) div 2) +1, r);
        end;
end;




procedure citire;
var i,x,y:longint;
begin
assign(input,'sequencequery.in'); reseT(input);
assign(output,'sequencequery.out'); rewritE(output);
readln(n,m);
for i:=1 to n do
        read(sir[i]);
build(1,1,n);

for i:=1 to m do
        begin
        readln(a,b);
        s:=0; ans:=-(1 shl 63)+100000000;
        query(1,1,n);
        writeln(ans);
        end;
close(input); closE(output);
end;


begin
citire;
end.