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;
     b1,b2:array [1..1 shl 17] of char;
     maxim,aux:int64;
     i,x,y,j,n,m: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:longint);
 var s,max:int64;
     i,mid: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');
 settextbuf(fi,b1); settextbuf(fo,b2);
 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 m do begin
                    readln(fi,x,y);
                     maxim:=-1000000; aux:=0;
                    query(1,1,n);
                    writeln(fo,maxim);
                    end;
  close(fo);
end.