RT

#include<bits/stdc++.h>
#define swap swapp 
using namespace std;
struct node{
	int l,r,id,t;
}q[5000005];
struct replace{
	int p,c;
}c[5000005];
int T,n,m,k,a[5000005],sum,cnt[5000005],ans[5000005],cnt1,cnt2,cur,aa;
inline void swapp(int x,int y){
	aa=x;
	x=y;
	y=aa;
}
inline void add(int x){
	cnt[a[x]]++;
	if(cnt[a[x]]==1)sum++;
}
inline void del(int x){
	if(cnt[a[x]]==1)sum--;
	cnt[a[x]]--;
}
inline int cmp(node x,node y){
	if(x.l/T!=y.l/T)return x.l<y.l;
	else if(x.r/T!=y.r/T)return x.r<y.r;
	return x.t<y.t;
}
inline void modify(int x,int t){ 
    if(c[t].p>=q[x].l&&c[t].p<=q[x].r){
        del(c[t].p);
        int tmp=a[c[t].p];
        a[c[t].p]=c[t].c;
        add(c[t].p);
        a[c[t].p]=tmp;
    }
    swap(a[c[t].p],c[t].c);  
    return;
}
int main(){
	scanf("%d%d",&n,&m);
	T=(int)pow(n,((double)2)/3);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=m;i++){
		char op;
		scanf("\n%c",&op);
		if(op=='Q'){
			cnt1++;
			scanf("%d%d",&q[cnt1].l,&q[cnt1].r);
			q[cnt1].t=cnt2;
			q[cnt1].id=cnt1;
		}
		if(op=='R'){
			cnt2++;
			scanf("%d%d",&c[cnt2].p,&c[cnt2].c);
		} 
	}
	sort(q+1,q+1+cnt1,cmp);
	int l=1,r=0;
	for(int i=1;i<=cnt1;i++){
		int ql=q[i].l,qr=q[i].r;
		while(l<ql)del(l),l++;
		while(l>ql)l--,add(l);
		while(r>qr)del(r),r--;
		while(r<qr)r++,add(r);
        while(cur<q[i].t){
        	cur++;
        	modify(i,cur);
		}
		while(cur>q[i].t){
        	modify(i,cur);
        	cur--;
		}
		ans[q[i].id]=sum;
	}
	for(int i=1;i<=cnt1;i++)
		printf("%d\n",ans[i]);
	return 0;
}