import sys input=sys.stdin.buffer.readline 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 & (r%2)): r>>=1 if not(f(self.op(self.d[r],sm))): while(r>1 for i in range(m,r): for j in range(len(X[i])): seg.set(X[i][j],e1) if l+1==r: que.append((l,r,k*2+1)) Y[k*2+1]=Y[k][:] for i in range(len(Y[k])): ANS[Y[k][i]]=r Y[k]=[] if C==N: break continue que.append((m,r,k*2+1)) que.append((l,m,k*2+2)) for i in range(len(Y[k])): ll,rr=LR[Y[k][i]][0],LR[Y[k][i]][1] v=seg.prod(ll,rr) if v[0]==ll-rr or v[0]-max(0,max(v[1],v[2],v[3])-1)<0: Y[k*2+2].append(Y[k][i]) else: Y[k*2+1].append(Y[k][i]) Y[k]=[] for i in range(l,m): for j in range(len(X[i])): seg.set(X[i][j],e1) for i in range(Q): ANS[i]=str(ANS[i]) print('\n'.join(ANS))