#include <bits/stdc++.h>
using namespace std;
const int N=133333+5;
const int M=1000000+5;
struct sdf{
	int id,l,r,t;
}q[N];
struct wer{
	int x,c;
}r[N];
int cntq=0,cntr=0;
int n,m,s;
int tot=0,num[M]={0};
int col[N],ans[N]={0};
bool cmp(sdf x,sdf y){
	if (x.l/s!=y.l/s)return x.l<y.l;
	if (x.r/s!=y.r/s)return x.r<y.r;
	return x.t<y.t;
}
void add(int x){
	if (num[x]==0)tot++;
	num[x]++;return ;
}
void del(int x){
	if (num[x]==1)tot--;
	num[x]--;return ;
}
void upd(int x,int y){
	if (q[x].l<=r[y].x&&r[y].x<=q[x].r){
		add(r[y].c);del(col[r[y].x]);
	}
	swap(r[y].c,col[r[y].x]);
	return ;
}
int main(){
	freopen ("nt2011_color.in","r",stdin);
	freopen ("nt2011_color.out","w",stdout);
	scanf("%d%d",&n,&m);s=pow(n,2.0/3);
	for (int i=1;i<=n;i++)scanf("%d",&col[i]);
	for (int i=1;i<=m;i++){
		char opt[5];int x,y;scanf("%s%d%d",opt,&x,&y);
		if (opt[0]=='Q'){cntq++;
			q[cntq]={cntq,x,y,cntr};
		}
		else{cntr++;
			r[cntr]={x,y};
		}
	}
	sort(q+1,q+cntq+1,cmp);
	int nowl=1,nowr=0,nowt=0;
	for (int i=1;i<=cntq;i++){
		while(nowl<q[i].l)del(col[nowl++]);
		while(nowl>q[i].l)add(col[--nowl]);
		while(nowr<q[i].r)add(col[++nowr]);
		while(nowr>q[i].r)del(col[nowr--]);
		while(nowt<q[i].t)upd(i,++nowt);
		while(nowt>q[i].t)upd(i,nowt--);
		ans[q[i].id]=tot;
	}
	for (int i=1;i<=cntq;i++)printf("%d\n",ans[i]);
	return 0;
}