// Arhiva de probleme - SequenceQuery
type
str = record A, L, R, S : int64; end;
var
n, m, i, t, a, b : longint;
v : array[0..1000000] of str;
f, g : text;
function max (a, b : int64) : int64;
begin
if (a > b) then max := a else max := b;
end;
function query (nod, st, dr, a, b : longint) : str;
var
s1, s2, s3: str;
mij, t : longint;
t1, t2, t3 : int64;
ok1, ok2: byte;
begin
if (a <= st) and (dr <= b) then
begin
query := v[nod]; exit;
end;
ok1 := 0; ok2 := 0;
mij := (st+dr) shr 1;
t := nod shl 1;
if (a <= mij) then
begin
s1 := query (t, st, mij, a, b);
ok1 := 1;
end;
if (mij < b) then
begin
s2 := query (t+1, mij+1, dr, a, b);
ok2 := 1;
end;
if (ok1 = 1) and (ok2 = 0) then
query := s1
else
if (ok1 = 0) and (ok2 = 1) then
query := s2
else
begin
t1 := s1.L; t2 := s1.S + s2.L;
if (t1 >= t2) then s3.L := t1 else s3.L := t2;
t1 := s2.R; t2 := s1.R + s2.S;
if (t1 >= t2) then s3.R := t1 else s3.R := t2;
t1 := s1.A; t2 := s2.A; t3 := s1.R + s2.L;
if (t1 >= t2) and (t1 >= t3) then s3.A := t1 else if (t2 >= t3) then s3.A := t2 else s3.A := t3;
s3.S := s1.S + s2.S;
query := s3;
end;
end;
procedure update (nod, st, dr, poz, val : longint);
var
mij, t : longint;
begin
if (st = poz) and (dr = poz) then
begin
v[nod].S := val; v[nod].A := val; v[nod].L := val; v[nod].R := val; exit;
end;
mij := (st + dr) shr 1;
t := nod shl 1;
if (poz <= mij) then
update (t, st, mij, poz, val);
if (mij < poz) then
update (t+1, mij+1, dr, poz, val);
v[nod].L := max (v[t].L, v[t].S + v[t+1].L);
v[nod].R := max (v[t + 1].R, v[t].R + v[t+1].S);
v[nod].A := max (max (v[t].A, v[t+1].A), v[t].R + v[t+1].L);
v[nod].S := v[t].S + v[t+1].S;
end;
begin
assign (f, 'sequencequery.in'); assign (g, 'sequencequery.out');
reset (f); rewrite (g);
readln (f, n, m);
for i := 1 to n do
begin
read (f, a);
update (1, 1, n, i, a);
end;
readln (f);
for i := 1 to m do
begin
readln (f, a, b);
writeln (g, query (1, 1, n, a, b).A);
end;
close (f); close (g);
end.