#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int f(1),x(0);
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
	for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
	return f*x;
}
inline int write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
	return 1;
}
const int N=1145141;
struct node{
	int l,r,t,k;
}q[N];
struct Retribution{
	int pos,col;
}Add[N];
int n,m,t,pos[N],ans[N],cnt[N],a[N],ANS(0),asksum(0),addsum(0),T(0),l=1,r=0;
inline bool cmp(const node &a,const node &b){
	if(pos[a.l]!=pos[b.l]){
		return pos[a.l]<pos[b.l];
	}
	if(pos[a.r]!=pos[a.r]){
		if(pos[a.l]%2==1) return pos[a.r]>pos[b.r];
		return pos[a.r]<pos[b.r];
	}
	return a.t<b.t;
}
inline void add(int x){     
	if(++cnt[a[x]]==1) ANS++;
}
inline void del(int x){
	if(--cnt[a[x]]==0) ANS--;
}
inline void TheWorld(int x){
	if(Add[x].pos<l||Add[x].pos>r){
		swap(Add[x].col,a[Add[x].pos]);
	}
	else{
		del(Add[x].pos);
		swap(Add[x].col,a[Add[x].pos]);
		add(Add[x].pos);
	}
}
char ch;
main(void){
	n=read(),m=read();
	t=pow(n,0.66666);
	for(register int i=1;i<=n;i++){
		a[i]=read();
		pos[i]=(i-1)/t+1;
	}
	for(register int i=1;i<=m;i++){
		cin>>ch;
		if(ch=='Q'){
			++asksum;
			q[asksum].l=read();
			q[asksum].r=read();
			q[asksum].k=asksum;
			q[asksum].t=addsum;
		}
		else {
			++addsum;
			Add[addsum].pos=read();
			Add[addsum].col=read();
		}
	}
	sort(q+1,q+asksum+1,cmp);
	for(register int i=1;i<=m;i++){
		while(l<q[i].l) del(l++);
		while(r>q[i].r) del(r--);
		while(l>q[i].l) add(--l);
		while(r<q[i].r) add(++r);
		while(q[i].t>T) TheWorld(++T);
		while(q[i].t<T) TheWorld(T--);
		ans[q[i].k]=ANS;
	}
	for(register int i=1;i<=asksum;i++){
		write(ans[i]),putchar('\n');
	}
	return 0;
}