const nmax=300000;
var f,g:text;
v1,v2,v3,sum,v:array[1..nmax]of longint;
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:longint);
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.