#include <bits/stdc++.h>
using namespace std;

#define INF 0x3f3f3f
#define RE register
#define maxn 50100
#define qwq cout<<"qwq";

int p=0,h[maxn],f[maxn],n,m,ans[maxn];
int bl,tot=0,cnt=0;

struct node{
	int l;
	int r;
	int id;
	int ti;
}ask[maxn];

struct nod{
	int st;
	int to;
	int time;
}ch[maxn];

inline void fread(int &x){
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	x*=f;
} 

inline bool cmp(node x,node y){
	if((x.l)/bl == (y.l)/bl)return x.r<y.r;
	else if(((x.l)/bl != (y.l)/bl)&&(x.l!=y.l)) return x.l<y.l;
	else return x.ti<y.ti;
}

inline void add(int x){
	p+=!h[f[x]]++;
}

inline void del(int x){
	p-=!--h[f[x]];
}

inline void update(int l,int r,int k){
	int x=ch[k].st;
	if(l<=x&&r>=x){
		del(x);
		add(ch[k].to);
	}
	swap(f[x],ch[k].to);
}

int main(){
	memset(h,0,sizeof(h));
	fread(n);
	fread(m);
	for(RE int i=0;i<n;i++)fread(f[i]);
	for(RE int i=1;i<=m;i++){
		char a;
		cin>>a;
		if(a=='Q'){
			fread(ask[++cnt].l);
			fread(ask[cnt].r);
			ask[cnt].r-=1;
			ask[cnt].ti=tot;
			ask[cnt].id=cnt;
		}
		if(a=='M'){
			fread(ch[++tot].st);
			fread(ch[tot].to);
			ch[tot].time=tot;
		}
	}
	bl=pow(n,0.666);
	sort(ask+1,ask+1+cnt,cmp);
	int l=1,r=0,k=0;
	for(RE int i=1;i<=cnt;i++){ 
		int lef=ask[i].l;
		int rig=ask[i].r;
		int t=ask[i].ti;
		//if(lef==3&&rig==4)cout<<l<<" "<<r<<" "<<p; 
		while(l<lef) add(l),l++;
		while(l>lef) l--,del(l);
		while(r>rig) del(r),r--;
		while(r<rig) r++,add(r);
		while(k<t) k++,update(l,r,k);
		while(k>t) update(l,r,k),k--;
		ans[ask[i].id]=p;
	}
	for(RE int i=1;i<=cnt;i++)printf("%d\n",ans[i]);
	return 0;
}

/*
7 4
1 2 1 3 2 1 4
Q 1 6
M 3 2
Q 1 6
Q 3 5

3
2
1
*/