Program sequencequery;
type tip=record
      a,b,ma,s:longint;
      end;
 var a:array [0..100001] of longint;
     aint:array [0..1 shl 18] of tip;
     n,m,i,j,x,y,val,pos,maxim,a1,k1,aux:longint;
     fi,fo:text;
function max(a,b:longint):longint;
 begin
  if a>b then max:=a else max:=b;
 end;
procedure update(nod,l,r:longint);
 var mid,s,i,max,st,s1:longint;
begin
 if l=r then begin aint[nod].a:=a[l]; aint[nod].b:=a[l]; aint[nod].ma:=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; st:=0;
                 for i:=l to r do begin
                                   aint[nod].s:=aint[nod].s+a[i];
                                   if s>0 then s:=s+a[i] else begin s1:=s; s:=a[i]; inc(st); end;
                                    if st=1 then aint[nod].a:=s1;
                                    if s>max then max:=s;
                                   end;
                 aint[nod].ma:=max; aint[nod].b:=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 m do begin
                    readln(fi,x,y);
                     maxim:=-1000000; aux:=-1000000;
                    query(1,1,n);
                    writeln(fo,maxim);
                    end;
  close(fo);
end.