Program sequencequery;
type tip=record
      a,b,ma,s:int64;
      end;
 var a:array [0..100001] of int64;
     aint:array [0..1 shl 18] of tip;
     n,m,j,x,y,pos,maxim,aux:int64;
     i:longint;
     fi,fo:text;
function max(a,b:int64):int64;
 begin
  if a>b then max:=a else max:=b;
 end;
procedure update(nod,l,r:int64);
 var mid,s,max:int64;
     i:longint;
begin
 if l=r then begin aint[nod].a:=a[l]; aint[nod].b:=a[l]; aint[nod].ma:=a[l]; aint[nod].s:=a[l]; end
        else begin
                mid:=(l+r) div 2;
                  update(2*nod,l,mid);
                    update(2*nod+1,mid+1,r);
                  s:=0; max:=-10000000;
                 for i:=l to r do begin
                                   aint[nod].s:=aint[nod].s+a[i];
                                   if s>0 then s:=s+a[i] else s:=a[i];
                                    if s>max then max:=s;
                                   end;
                 aint[nod].ma:=max; aint[nod].b:=s;  s:=0;
                 for i:=r downto l do if s>0 then s:=s+a[i] else s:=a[i];
                 aint[nod].a:=s;
                end;
 end;
procedure query(nod,l,r:longint);
 var mid:longint;
begin
 if (x<=l) and (y>=r) then begin
                            maxim:=max(maxim,max(aint[nod].ma,aint[nod].a+aux));
                             aux:=max(aux+aint[nod].s,aint[nod].b);
                             end
                 else begin
                       mid:=(l+r) div 2;
                        if x<=mid then query(2*nod,l,mid);
                        if y>mid then query(2*nod+1,mid+1,r);
                       end;
end;
begin
 assign(fi,'sequencequery.in');
  assign(fo,'sequencequery.out');
 reset(fi); rewrite(fo); readln(fi,n,m);
  for i:=1 to n do read(fi,a[i]); readln(fi);
    update(1,1,n);
{ for i:=1 to 2*n do writeln(fo,aint[i].a,'   ',aint[i].b,'   ',aint[i].ma,'   ',aint[i].s);     }
  for i:=1 to m do begin
                    readln(fi,x,y);
                     maxim:=-1000000; aux:=0;
                    query(1,1,n);
                    writeln(fo,maxim);
                    end;
  close(fo);
end.