#include<bits/stdc++.h>
using namespace std;
#define _ =read()
inline int read(){ 
	int r=0,W=1; 
	char ch=getchar(); 
	while(ch>'9'||ch<'0') { if(ch=='-') W=-1; ch=getchar();} 
	while(ch>='0'&&ch<='9') { r=r*10+ch-'0'; ch=getchar();} 
	return r*W;
} 

int n;
int m;
int now;
int tot;
int cnt;

int a[140100];
int ton[1000001];
int ans[140010];
int belong[140001];
struct ss {
	int l;
	int r;
	int id;
	int pr;
}Q[501000];
struct S{
	int pos;
	int k;
}C[501000];


bool comp(ss a,ss b){
	if(belong[a.l]!=belong[b.l]) return a.l<b.l;
	if(belong[a.r]!=belong[b.r]) return a.r<b.r;
	return a.pr<b.pr;
}
void add(int x){
	if(ton[a[x]]==0) now++;
	ton[a[x]] ++;
}
void de(int x){
	ton[a[x]]--;
	if(ton[a[x]]==0) now--;
}
void Swap(int &x,int &y){
	int z;
	z=x;
	x=y;
	y=z;
}
void chenge(int kk,int i){
	if(C[kk].pos>=Q[i].l&&C[kk].pos<=Q[i].r){
		--ton[a[C[kk].pos]];
		if(ton[a[C[kk].pos]]==0) now--;
		++ton[C[kk].k];
		if(ton[C[kk].k]==1) now++;
	}
	Swap(C[kk].k,a[C[kk].pos]);
}

inline int XWZY__(){
	n _;
	m _;
	int base=sqrt(n);
	int num=ceil((n*1.0)/(base*1.0));
	for(int i=1;i<=num;i++){
		for(int j=num*(i-1)+1;j<=num*i;j++){
			belong [j] = i; 
		}
	}
	for(int i=1;i<=n;i++){
		a[i] _;
	}
	
	for(int i=1;i<=m;i++){
		char Opt;
		cin>>Opt;
		if(Opt=='Q'){
			Q[++cnt].l _;
			Q[cnt].r _;
			Q[cnt].id=cnt;
			Q[cnt].pr=tot;
		}
		else {
			C[++tot].pos _;
			C[tot].k _;
		}
	}
	sort(Q+1,Q+cnt+1,comp);
	
	tot=0;
	int l=1;
	int r=0;
	
	for(int i=1;i<=cnt;i++){
		while(Q[i].l>l){
			de(l++);
		}
		while(Q[i].l<l){
			add(--l);
		}
		
		while(Q[i].r>r){
			add(++r);
		}
		
		while(Q[i].r<r){
			de(r--);
		}
		while(tot<Q[i].pr) chenge(++tot,i);
		while(tot>Q[i].pr) chenge(tot--,i);
		ans[Q[i].id]=now;
	}
	
	for(int i=1;i<=cnt;i++){
		printf("%d\n",ans[i]);	
	}
	return 0;
}
int XWZY_=XWZY__();
signed main(){;}