(n,*c),a,*q=$<.map{_1.split.map &:to_i}
b=(0..n).map{_1&-_1}
d=b.map{[]}
q.map{d[_2]<<[_1-1,$.+=1]}
u=i=0
a.map{t=c[_1]
(b[t]-=1;t+=t&-t)until t ?t>n:u+=1
c[_1]=i+=1
d[i].map{|x,y|s=u
(s-=b[x];x&=x-1)while x>0
$*[y]=s}}
puts$*