import collections,sys,math,functools,operator,itertools,bisect,heapq,decimal,string,time,random #https://github.com/shakayami/ACL-for-python/blob/master/segtree.py class segtree(): n=1 size=1 log=2 d=[0] op=None e=10**15 def __init__(self,V,OP,E): self.n=len(V) self.op=OP self.e=E self.log=(self.n-1).bit_length() self.size=1<>i) def get(self,p): assert 0<=p and p>=1 r>>=1 return self.op(sml,smr) def all_prod(self): return self.d[1] def max_right(self,l,f): assert 0<=l and l<=self.n assert f(self.e) 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>i) self.d[p]=x for i in range(1,self.log+1):self.update(p>>i) def get(self,p): assert 0<=p and p>i) return self.d[p] def prod(self,l,r): assert 0<=l and l<=r and r<=self.n if l==r:return self.e l+=self.size r+=self.size for i in range(self.log,0,-1): if (((l>>i)<>i) if (((r>>i)<>i) sml,smr=self.e,self.e while(l>=1 r>>=1 return self.op(sml,smr) def all_prod(self):return self.d[1] def apply_point(self,p,f): assert 0<=p and p>i) self.d[p]=self.mapping(f,self.d[p]) for i in range(1,self.log+1):self.update(p>>i) def apply(self,l,r,f): assert 0<=l and l<=r and r<=self.n if l==r:return l+=self.size r+=self.size for i in range(self.log,0,-1): if (((l>>i)<>i) if (((r>>i)<>i) l2,r2=l,r while(l>=1 r>>=1 l,r=l2,r2 for i in range(1,self.log+1): if (((l>>i)<>i) if (((r>>i)<>i) def max_right(self,l,g): assert 0<=l and l<=self.n assert g(self.e) if l==self.n:return self.n l+=self.size for i in range(self.log,0,-1):self.push(l>>i) sm=self.e while(1): while(l%2==0):l>>=1 if not(g(self.op(sm,self.d[l]))): while(l>i) sm=self.e while(1): r-=1 while(r>1 and (r%2)):r>>=1 if not(g(self.op(self.d[r],sm))): while(r= 1: st.set(a[r],st.get(a[r])-1) break r += 1 z = r-l+1 zz = n-l+1 #print(l,z,zz) if z <= zz: lst.apply(z,zz,1) if r - l >= 1: st.set(a[l],st.get(a[l])-1) else: r += 1 for i in range(1,n+1): print(lst.get(i))