#include<bits/stdc++.h>
using namespace std;
const int N=133335;
struct node{
	int l,r,t,id;
}q[N];
struct nd{
	int p,c;
}o[N];
int cnt1,cnt2,out[N],cnt[N],a[N],ans,k;
bool cmp(node x,node y){
	if(x.l/k!=y.l/k)return x.l<y.l;
	if(x.r/k!=y.r/k)return x.r<y.r;
	return x.t<y.t;
}
void add(int x){
	if(++cnt[x]==1)ans++;
}
void del(int x){
	if(--cnt[x]==0)ans--;
}
void td(int x,int t){
	if(q[x].l<=o[t].p&&o[t].p<=q[x].r){
		del(a[o[t].p]);
		add(o[t].c);
	}
	swap(a[o[t].p],o[t].c);
}
int main(){
	int n,m;
	cin>>n>>m;
	k=pow(n,0.666);
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++){
		char x;
		int l,r;
		cin>>x>>l>>r;
		if(x=='Q')cnt1++,q[cnt1].l=l,q[cnt1].r=r,q[cnt1].id=cnt1,q[cnt1].t=cnt2;
		else cnt2++,o[cnt2].p=l,o[cnt2].c=r;
	}
	sort(q+1,q+cnt1+1,cmp);
	int l=1,r=0,t=0;
	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(t<q[i].t)td(i,++t);
		while(t>q[i].t)td(i,t--);
		out[q[i].id]=ans;
	}
	for(int i=1;i<=cnt1;i++)cout<<out[i]<<endl;
	return 0;
}