program maxq;
const fi='sequencequery.in'; fo='sequencequery.out';
var v:array[1..100000]of longint;
    a,b,c,sum:array[1..300000]of real;
    f,g:text;
    i,n,m,x,y:longint;
    lf,rt:longint;
    ans,s:real;
function maxim(a,b:real):real;
begin
if a>b then maxim:=a
   else maxim:=b;
end;

procedure build(n,st,dr:longint);
var mij:longint;
    lf,rt:longint;
begin
if(st=dr) then begin
   A[n]:=v[st];
   B[n]:=A[n];
   C[n]:=A[n];
   Sum[n]:=v[st];
  end
  else begin
        mij:=(st+dr)shr 2;
        lf:=n shl 1; rt:=n shl 1+1;
        build(lf,st,mij);
        build(rt,mij+1,dr);

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

procedure query(n,st,dr:longint);
var mij:longint;
    lf,rt:longint;
begin
if(st>=x)and(dr<=y) then begin
    ans:=maxim(maxim(ans,S+A[n]),C[n]);
    S:=maxim(S+Sum[n],B[n]);
   end
  else begin
         mij:=(st+dr)shr 2;
         lf:=n shl 1; rt:=n shl 1+1;
         if(x<=mij) then query(lf,st,mij);
         if(y>mij) then query(rt,mij+1,dr);
       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]);
build(1,1,n);
readln(f);
for i:=1 to m do begin
     readln(f,x,y);
     S:=0;Ans:=-1000000;
     query(1,1,n);
     writeln(g,ans:0:0);
   end;
close(g);
close(f);
end.