#include<bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define re register
const int N=1000010;
int n,m,sum,cnt[N],len,a[N];
int ans[N];
int time_upd,time_que;
struct update{
	int place,color,pre;
}u[N];
struct query{
	int t,own_t,l,r;
}q[N];
il int fnd(int x){
	return x/len;
}
il bool cmp(query x,query y){
	int fx=fnd(x.l),fy=fnd(y.l);
	if(fx!=fy)return fx<fy;
	fx=fnd(x.r),fy=fnd(y.r);
	if(fx!=fy)return fx<fy;
	return x.t<y.t;
}
il void del(int x){
	cnt[x]--;
	if(!cnt[x])sum--;
}
il void add(int x){
	if(!cnt[x])sum++;
	cnt[x]++;
}
il int read(){
    re int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
signed main(){
	n=read(),m=read();
	for(re int i=1;i<=n;i++)a[i]=read();
	for(re int i=1;i<=m;i++){
		char op;
		cin>>op;
		if(op=='Q'){
			++time_que;
			int x=read(),y=read();
			q[time_que]={time_upd,time_que,x,y};
		}
		else{
			++time_upd;
			int x=read(),y=read();
			u[time_upd]={x,y,a[x]};
		}
	}
	len=pow(n,0.66);
	sort(q+1,q+1+time_que,cmp);
	for(re int l=1,r=0,time=0,id=1;id<=time_que;id++){
		while(l>q[id].l)add(a[--l]);
		while(r<q[id].r)add(a[++r]);
		while(l<q[id].l)del(a[l++]);
		while(r>q[id].r)del(a[r--]);
		while(time>q[id].t){
			int pla=u[time].place;
			if(pla>=l&&pla<=r)del(a[pla]);
			a[pla]=u[time].pre;
			if(pla>=l&&pla<=r)add(a[pla]);
			time--;
		}
		while(time<q[id].t){
			++time;
			int pla=u[time].place;
			if(pla>=l&&pla<=r)del(a[pla]);
			a[pla]=u[time].color;
			if(pla>=l&&pla<=r)add(a[pla]);
		}
		ans[q[id].own_t]=sum;
	}
	for(re int i=1;i<=time_que;i++)printf("%lld\n",ans[i]);
    return 0;
}