const nmax=300000;
var f,g:text;
v1,v2,v3,sum,v:array[1..nmax]of int64;
s,max,pc,uc,a,m,l,nod,poz,b,n,i,j,x:longint;

function maxim(a,b:longint):longint;
begin
if a>b then maxim:=a
   else maxim:=b;
end;
procedure actualizare(nod,st,dr:longint);
var mij:longint;
begin
  if st=dr then
    begin
    v[nod]:=x;
    v1[nod]:=v[nod];
    v2[nod]:=v[nod];
    sum[nod]:=x;
    end
    else
      begin
      mij:=(st+dr)div 2;
      if poz<=mij then actualizare(2*nod,st,mij)
      else actualizare(2*nod+1,mij+1,dr);
      v[nod]:=maxim(v[2*nod],v[2*nod+1]+sum[2*nod]);
      v1[nod]:=maxim(v1[2*nod]+sum[2*nod+1],v1[2*nod+1]);
      v2[nod]:=maxim(maxim(v2[2*nod],v2[2*nod+1]),v1[2*nod]+v[2*nod+1]);
      sum[nod]:=sum[2*nod]+sum[2*nod+1];
      end;
end;

procedure caut(nod,st,dr:integer);
var mij:longint;
begin
if (a<=st) and (dr<=b) then
               begin
               if s<0 then s:=0;
               max:=maxim(max,maxim(s+v[nod],v2[nod]));
               s:=maxim(s+sum[nod],v1[nod]);
               end
  else
     begin
     mij:=(st+dr)shr 1;
     if (a<=mij) then caut(2*nod,st,mij);
     if (mij<b) then caut(2*nod+1,mij+1,dr);
     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
begin
read(f,x);
poz:=i;
actualizare(1,1,n);
end;

for i:=1 to m do
   begin
      readln(f,a,b);
      s:=0;
      max:=-1000000000;
      caut(1,1,n);
      writeln(g,max);
      end;
close(g);
end.