program vijos1083;
type seg=record
nmax,lmax,rmax,sum:longint
end;
var
dat:array[1..1200000] of seg;
i,j,k,l,m,n,p1,p2,p3:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
function max3(a,b,c:longint):longint;
begin
if a>max(b,c) then exit(a) else exit(max(b,c));
end;
procedure updata(var a:seg;b,c:seg);
begin
with a do
begin
lmax:=max(b.lmax,b.sum+c.lmax);
rmax:=max(c.rmax,c.sum+b.rmax);
nmax:=max3(b.nmax,c.nmax,b.rmax+c.lmax);
sum:=b.sum+c.sum;
end;
end;
procedure build(node,l,r:longint);
var
mid:longint;
begin
if l=r then begin
with dat[node] do
begin read(sum);lmax:=sum;rmax:=sum;nmax:=sum end;
exit
end;
mid:=(l+r)>>1;
build(node*2,l,mid);
build(node*2+1,mid+1,r);
updata(dat[node],dat[node*2],dat[node*2+1])
end;
procedure insert(node,l,r:longint);
begin
if (l=r) and (l=p2) then begin
with dat[node] do begin
sum:=p3;
lmax:=sum;
rmax:=sum;
nmax:=sum
end;
exit
end;
if (l+r) shr 1>=p2 then insert(node*2,l,(l+r) shr 1) else
insert(node*2+1,(l+r) shr 1+1,r);
updata(dat[node],dat[node*2],dat[node*2+1]);
end;
function ask(node,l,r:longint):seg;
var mid:longint; a,b:seg;
begin
if (l>=p2) and (r<=p3) then exit(dat[node]);
mid:=(l+r)>>1;
if mid>=p2 then a:=ask(node*2,l,mid);
if mid<p3 then b:=ask(node*2+1,mid+1,r);
if mid>=p3 then exit(a);
if mid<p2 then exit(b);
updata(ask,a,b);
end;
begin
readln(n,m);
build(1,1,n);
for i:=1 to m do
begin
readln(p1,p2,p3);
if p1=1 then begin
if p2>p3 then 
begin l:=p2; p2:=p3; p3:=l end;writeln(ask(1,1,n).nmax,' ') end else
insert(1,1,n);
end;
end.