#include<bits/stdc++.h>
//#define int long long
using namespace std;
int n,c,m,siz,t,tot,ans[150005],cnt[1000005],p[150005],block,pos[150005],l=1,r,n1,n2;
struct query{
	int l,r,id,q;
}tt[150005];
struct R{
	int x,y;
}b[150005];
bool cmp(query a,query b){
	if(pos[a.l]==pos[b.l]) return (p[a.r]==p[b.r]?a.id<b.id:a.l<b.l);
	return a.l<b.l;
}
void add(int x){
	if(cnt[x]==0) tot++;
	cnt[x]++;
}
void del(int x){
	if(cnt[x]==1) tot--;
	cnt[x]--;
}
void change(int x,int now){
	int id=b[now].x;
	if(tt[x].l<=id&&id<=tt[x].r){
		del(p[id]);
		add(b[now].y);
	}
	swap(p[id],b[now].y);
}
signed main(){
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=m;i++){
    	char op;
    	int l,r,id=i;
    	cin>>op>>l>>r;
    	if(op=='Q') tt[++n1]={l,r,n2,n1};
    	else b[++n2]={l,r};
	}
    block=(int)ceil(pow(n,2.0/3.0)),siz=n%block?n/block+1:block;
    for(int i=1;i<=siz;i++){
    	int l=(i-1)*block+1,r=min(n,i*block);
    	for(int j=l;j<=r;j++) pos[j]=i;
	}
	sort(tt+1,tt+1+n1,cmp);
	for(int i=1;i<=n1;i++){
		while(l>tt[i].l) add(p[--l]);
		while(l<tt[i].l) del(p[l++]);
		while(r<tt[i].r) add(p[++r]);
		while(r>tt[i].r) del(p[r--]);
		while(t<tt[i].id) change(i,++t);
		while(t>tt[i].id) change(i,t--);
		ans[tt[i].q]=tot;
	}
	for(int i=1;i<=n1;i++) cout<<ans[i];
}