program sequencequery;
const fi='sequencequery.in';fo='sequencequery.out';
var v:array[1..100000] of longint;
    a,b,c,sum:array[1..240000]of real;
    n,m,x,y:longint;
    i:longint;
    ans,S:real;

    f,g:text;
function max(a,b:real):real;
begin
if a>b then max:=a
   else max:=b
end;

procedure build(n,l,r:longint);
var mij:longint;
    lf,rt:longint;
begin
if l=r then begin
    A[n]:=v[l];
    B[n]:=v[l];
    C[n]:=v[l];
    sum[n]:=V[l];
   end
   else begin
     mij:=(l+r) shr 1;
     lf:=n shl 1;rt:=n shl 1+1;

     build(lf,l,mij);
     build(rt,mij+1,r);

     A[n]:=max(A[lf],sum[lf]+A[rt]);
     B[n]:=max(B[rt],B[lf]+sum[rt]);
     C[n]:=max(max(C[lf],C[rt]),B[lf]+A[rt]);
     sum[n]:=sum[lf]+sum[rt];
   end;
end;

procedure query(n,l,r:longint);
var mij:longint;
    lf,rt:longint;
begin
lf:=n shl 1;rt:=n shl 1+1;
if(l>=x)and(r<=y)then begin
    ans:=max(ans,max(C[n],S+A[n]));
    S:=max(S+sum[n],B[n]);
   end
   else begin
    mij:=(l+r) shr 1;
    if x<=mij then query(lf,l,mij);
    if y>mij then query(rt,mij+1,r);
   end;
end;

begin
assign(f,fi);reset(f);
assign(g,fo);rewrite(g);
readln(f,n,m);
for i:=1 to n do read(f,v[i]);
readln(f);
build(1,1,n);
for i:=1 to m do begin
      readln(f,x,y);
      ans:=-100000;S:=0;
      query(1,1,n);
      writeln(g,ans:0:0);
    end;
close(g);
close(f);
end.