#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int res=0;
    char c;
    bool zf=0;
    while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c=='-')zf=1;
    else res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0';
    if(zf)return -res;
    return res;
}
struct op1{
	int pos,val;
}c[133334];
struct op2{
	int l,r,id,t;
}ask[133334];
int cr,askr;
int col[133334],cnt[1000005],bel[133334],ans[133334];
inline bool cmp(op2 x,op2 y){
	return (bel[x.l]^bel[y.l]?bel[x.l]<bel[y.l]:(bel[x.r]^bel[y.r]?bel[x.r]<bel[y.r]:x.t<y.t));
}
signed main(){
	int n=read(),m=read();
	for(register int i=1;i<=n;++i){
		col[i]=read();
	}
	for(register int i=1;i<=m;++i){
		char cc;
		while((cc=getchar())!='Q'&&cc!='R');
		if(cc=='Q'){
			ask[++askr].l=read(),ask[askr].r=read(),ask[askr].id=askr,ask[askr].t=cr;
		}
		else{
			c[++cr].pos=read(),c[cr].val=read();
		}
	}
	int size=exp((log(n)+log(cr))/3);
	for(register int i=1;i<=n;++i){
		bel[i]=(i-1)/size+1;
	}
	sort(ask+1,ask+askr+1,cmp);
	int l=1,r=0,t=0,nowans=0;
	for(register int i=1;i<=n;++i){
		while(l<ask[i].l)nowans-=!(--cnt[col[l++]]);
		while(l>ask[i].l)nowans+=!(cnt[col[--l]]++);
		while(r<ask[i].r)nowans+=!(cnt[col[++r]]++);
		while(r>ask[i].r)nowans-=!(--cnt[col[r--]]);
		while(t<ask[i].t){++t;
			if(l<=c[t].pos&&c[t].pos<=r)nowans+=!(cnt[c[t].val]++)-!(--cnt[col[c[t].pos]]);
			swap(col[c[t].pos],c[t].val);
		}
		while(t>ask[i].t){
			if(l<=c[t].pos&&c[t].pos<=r)nowans+=!(cnt[c[t].val]++)-!(--cnt[col[c[t].pos]]);
			swap(col[c[t].pos],c[t].val);
			--t;} 
		ans[ask[i].id]=nowans;
	}
	for(register int i=1;i<=askr;++i){
		printf("%d\n",ans[i]);
	}
	return 0;
}