program p1659;

var

a,sum,left,right:array[1..1000000] of longint;

i,j,k,n,m,x,y,z:longint;

function max(x,y:longint):longint;

begin

if x>y then exit(x)

else exit(y);

end;

procedure creat(root,h,t:longint);

var

m:longint;

begin

if h>t then exit;

left[root]:=h;

right[root]:=t;

if h=t then sum[root]:=a[h]

else

begin

m:=(h+t) div 2;

creat(root*2,h,m);

creat(root*2+1,m+1,t);

sum[root]:=max(sum[root*2],sum[root*2+1]);

end;

end;

procedure change(root,h,t,num:longint);

begin

if (left[root]>t)or(right[root]t)or(right[root]=h)and(right[root]