// 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 query   (nod, st, dr : 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);
    ok1 := 1;
    end;
if (mij < b) then
    begin
	s2 := query (t+1, mij+1, dr);
    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 : longint);
var
    mij, t : longint;
	t1, t2, t3 : int64;
begin
if (st = a) and (dr = a) then
	begin
	v[nod].S := b; v[nod].A := b; v[nod].L := b; v[nod].R := b;	exit;
	end;
mij := (st + dr) shr 1;
t := nod shl 1;
if (a <= mij) then
	update (t, st, mij);
if (mij < a) then
	update (t+1, mij+1, dr);
t1 := v[t].L; t2 := v[t].S + v[t + 1].L;
if (t1 >= t2) then v[nod].L := t1 else v[nod].L := t2;
t1 := v[t + 1].R; t2 := v[t].R + v[t + 1].S;
if (t1 >= t2) then v[nod].R := t1 else v[nod].R := t2;
t1 := v[t].A; t2 := v[t + 1].A; t3 :=  v[t].R + v[t + 1].L;
if (t1 >= t2) and (t1 >= t3) then v[nod].A := t1 else if (t2 >= t3) then v[nod].A := t2 else v[nod].A := t3;
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 a := 1 to n do
	begin
	read 	(f, b);
	update	(1, 1, n);
	end;
readln	(f);
for i := 1 to m do
	begin
	readln	(f, a, b);
    writeln	(g, query (1, 1, n).A);
	end;
close	(f);				close	(g);
end.