#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int c[N],a[N],ans[N],b[N],sum=0,n,m,maxx,cnt1=0,cnt2=0;
struct tip_q{int l,r,id,t;}q[N];
struct tip_r{int p,col;}p[N];
inline bool cmp(tip_q a,tip_q b){
	if(a.l/maxx!=b.l/maxx)return a.l<b.l;
	else return (a.l/maxx)&1?a.r<b.r:a.r>b.r;
}
void add(int x){if(c[x]==0){++sum;}++c[x];}
void del(int x){--c[x];if(c[x]==0){--sum;}}
int main(){
	cin>>n>>m,maxx=pow(n,(double)2/(double)3);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
	for(int i=1;i<=m;i++){
		char c;cin>>c;
		if(c=='Q')scanf("%d%d",&q[++cnt1].l,&q[cnt1].r),q[cnt1].id=i,q[cnt1].t=cnt2;
		else scanf("%d%d",&p[++cnt2].p,&p[cnt2].col);
	}
	sort(q+1,q+1+cnt1,cmp);
	for(int i=1,l=1,r=0,t=0;i<=cnt1;++i){
		while(l>q[i].l)add(a[--l]);
		while(r<q[i].r)add(a[++r]);
		while(l<q[i].l)del(a[l++]);
		while(r>q[i].r)del(a[r--]);
		for(;t>q[i].t;){
			if(l<=p[t].p&&p[t].p<=r)del(a[p[t].p]),a[p[t].p]=b[p[t].p],add(a[p[t].p]);
			else a[p[t].p]=b[p[t].p];--t;
		}
		for(;t<q[i].t;){
			++t;if(l<=p[t].p&&p[t].p<=r)del(a[p[t].p]),a[p[t].p]=p[t].col,add(a[p[t].p]);
			else a[p[t].p]=p[t].col;
		}
		ans[q[i].id]=sum;
	}
	for(int i=1;i<=cnt1;i++)printf("%d\n",ans[i]);
	return 0;
}