// Arhiva de probleme - SequenceQuery
type
	str = record A, L, R, S : int64; end;
var
	n, m, i, t, a, b, q : 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;
    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
	s3.L := max (s1.L, s1.S + s2.L);
	s3.R := max (s2.R, s1.R + s2.S);
	s3.A := max (max (s1.A, s2.A), s1.R + s2.L);
	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.