(N,),C,*L=$<.map{_1.split.map &:to_i};
W=[0]*-~N;
X=->x{x>0?W[x]+X[x&x-1]:0}
Y=->x,y{(W[x]+=y;x+=x&-x)while x&.<=N}
q,*A=0;
G=[];
L.map{[_2,_1,$.+=1]}.sort.map{|r,l,j|
(q+1..r).map{
Y[G[c=C[_1-1]],-1];Y[G[c]=_1,1]
};
A[j]=X[q=r]-X[l-1]
};
puts A
