program seq;
var A,B,C,Sum : array [1..300000] of longint;
    V : array [1..100000] of longint;
    i,n,m,j,p1,p2,S,ans : longint;
    f,g : text;
function max(a,b:longint):longint;
begin
if a>b then max := a
        else max := b;
end;

procedure build(nod,l,r:longint);
var mij : longint;
begin
if l=r then begin
            A[nod] := V[l];
            B[nod] := V[l];
            C[nod] := V[l];
            Sum[nod] := V[l];
            end
else begin
     mij := (l+r) div 2;
     build(2*nod,l,mij);
     build(2*nod+1,mij+1,r);

     A[nod] := max(A[2*nod],Sum[2*nod]+A[2*nod+1]);
     B[nod] := max(B[2*nod+1],Sum[2*nod+1]+B[2*nod]);
     C[nod] := max(max(C[2*nod],C[2*nod+1]),B[2*nod]+A[2*nod+1]);
     Sum[nod] := Sum[2*nod]+Sum[2*nod+1];
     end;
end;

procedure query(nod,l,r:longint);
var mij : longint;
begin
if (p1<=l) and (r<=p2) then begin
                            if S<0 then S := 0;
                            ans := max(S+A[nod],C[nod]);
                            S := max(S+Sum[nod],B[nod]);
                            end
else begin
        mij := (l+r) div 2;
        if p1<=mij then query(2*nod,l,mij);
        if mij<p2 then query(2*nod+1,mij+1,r);
        end;
end;

begin
assign(f,'sequencequery.in');
reset(f);
assign(g,'sequencequery.out');
rewrite(g);

readln(f,n,m);

for i := 1 to n do
read(f,V[i]);
build(1,1,n);
readln(f);

for i := 1 to m do begin
readln(f,p1,p2);
S := 0;
ans := 0;
query(1,1,n);
writeln(g,ans);
end;
close(f);
close(g);
end.