class segtree(): n=size=1;d,op,e=[0],None,10**15 def __init__(self,V,OP,E): self.n=len(V);self.op=OP;self.e=E;self.size=1<<(self.n-1).bit_length();self.d=[E]*2*self.size for i in range(self.n):self.d[self.size+i]=V[i] for i in range(self.size)[::-1]:self.update(i) def __setitem__(self,p,x): p+=self.size;self.d[p]=x while p:p>>=1;self.update(p) def __getitem__(self,p):return self.d[p+self.size] def prod(self,l,r): sml=smr=self.e;l+=self.size;r+=self.size while l>=1;r>>=1 return self.op(sml,smr) def all_prod(self):return self.d[1] def max_right(self,l,f): if l==self.n:return self.n l+=self.size;sm=self.e while 1: while l%2==0:l>>=1 if not f(self.op(sm,self.d[l])): while l1 and r%2:r>>=1 if not f(self.op(self.d[r],sm)): while r