// Arhiva de probleme - SequenceQuery
type
	str = record  A, L, R, S: int64; end;
var
	n, m, i, t, aa,bb, m2 : longint;
	A, L, R, S : array[0..1000000] of int64;
	ss : array[1..1000000] of char;
	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 (aa <= st) and (dr <= bb) then
	begin
	query.A := a[nod];
    query.L := l[nod];
    query.R := r[nod];
    query.S := s[nod];
    exit;
	end;
ok1  := 0; ok2  := 0;
mij := (st+dr) shr 1;
t := nod shl 1;
if (aa <= mij) then
    begin
    s1 := query (t, st, mij);
    ok1 := 1;
    end;
if (mij < bb) 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 = aa) and (dr = aa) then
	begin
	S[nod] := bb; A[nod] := bb; L[nod] := bb; R[nod] := bb;	exit;
	end;
mij := (st + dr) shr 1;
t := nod shl 1;
if (aa <= mij) then
	update (t, st, mij);
if (mij < aa) then
	update (t+1, mij+1, dr);
t1 := L[t]; t2 := s[t] + L[t + 1];
if (t1 >= t2) then L[nod] := t1 else L[nod] := t2;
t1 := R[t + 1]; t2 := R[t] + S[t + 1];
if (t1 >= t2) then R[nod] := t1 else R[nod] := t2;
t1 := A[t]; t2 := A[t + 1]; t3 :=  R[t] + L[t + 1];
if (t1 >= t2) and (t1 >= t3) then A[nod] := t1 else if (t2 >= t3) then A[nod] := t2 else A[nod] := t3;
S[nod] := s[t] + S[t + 1];

end;

begin
assign	(f, 'sequencequery.in');	assign 	(g, 'sequencequery.out');
reset	(f);						rewrite	(g);
readln	(f, n, m);
read    (f, ss);
i:=1; bb := 0;
while (ss[i] <> #0) do
    begin
    bb := 0; inc(aa);
	m2:=1;
    if (ss[i] = #45) then
        begin
        m2 := -1;
        inc(i);
        end;
    while (ss[i] <> #0) and (ss[i] <> #32) do
        begin
        bb := bb*10+ord(ss[i])-48;
        inc(i);
        end;
    bb := bb*m2;
	update	(1, 1, n);
    inc(i);
    end;

	readln	(f);
for i := 1 to m do
	begin
	readln	(f, aa, bb);
    writeln	(g, query (1, 1, n).A);
	end;
close	(f);				close	(g);
end.