#pragma GCC optimize("Ofast","-funroll-loops")
#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
#include <bits/stdc++.h>
using namespace std;
const int N=(int)1e6+50;
int n,m,a[N],block,ans[N],pos[N];
int cnt1,cnt2,L=1,R=0,now=0,Ans,cnt[N];
char c[10];
struct change{int P,col;}p[N];
struct node{int L,R,t,id;}q[N];
inline void del(int x){
	--cnt[x];
	if(cnt[x]==0) --Ans; 
}
inline void add(int x){
	++cnt[x];
	if(cnt[x]==1) ++Ans;
}
inline void modify(int x,int ti){
	if(p[ti].P>=q[x].L&&p[ti].P<=q[x].R){
		del(a[p[ti].P]);
		add(p[ti].col);
	}
	swap(a[p[ti].P],p[ti].col);
}
inline bool cmp(node a,node b){
	if(pos[a.L]!=pos[b.L]) return a.L<b.L;
	else if(pos[a.L]&1&&a.R!=b.R) return a.R<b.R;
	else if(a.R!=b.R) return a.R>b.R;
	else return a.t<b.t;
}
inline int read(){
	int cnt=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){cnt=(cnt<<1)+(cnt<<3)+(c^48);c=getchar();}
	return cnt*f;
}
signed main(){
	n=read(),m=read();block=pow(n,0.666666);
	for(int i=1;i<=n;++i){a[i]=read();pos[i]=(i-1)*block+1;}
	for(int i=1;i<=m;++i){
		scanf("%s",c+1);//cnt2代表当前修改数  t代表在这次询问之前修改了多少次 
		if(c[1]=='Q'){q[++cnt1].L=read(),q[cnt1].R=read();q[cnt1].t=cnt2;q[cnt1].id=cnt1;}
		if(c[1]=='R'){p[++cnt2].P=read(),p[cnt2].col=read();}
	}
	sort(q+1,q+1+cnt1,cmp);
	for(int i=1;i<=cnt1;++i){
		while(L>q[i].L) add(a[--L]);
		while(L<q[i].L) del(a[L++]);
		while(R>q[i].R) del(a[R--]);
		while(R<q[i].R) add(a[++R]);
		while(now<q[i].t) modify(i,++now);
		while(now>q[i].t) modify(i,now--);
		ans[q[i].id]=Ans;
	}
	for(int i=1;i<=cnt1;++i){cout<<ans[i]<<endl;}
	return 0;
}