#include<bits/stdc++.h>
using namespace std;
const int MM=2000006;
int n,bs,a[MM],b[MM],num[MM],answer[MM],cnt,ans,l,r,t;
char ch;
struct que
{
	int l,r,t;
}q[MM];
struct update
{
	int p,x,t;
}u[MM];
void add(int p)
{
	if(!num[a[p]])ans++;
	num[a[p]]++;
}
void del(int p)
{
	if(num[a[p]]==1)ans--;
	num[a[p]]--;
}
void upd(int t)
{
	if(!u[t].p)
		return;
	if(u[t].p<=r&&u[t].p>=l)	
	{
		del(u[t].p);
		if(!num[u[t].x])ans++;
		num[u[t].x]++;
	}
} 
void und(int t)
{
	if(!u[t].p)
		return;
	if(u[t].p<=r&&u[t].p>=l)	
	{
		add(u[t].p);
		if(num[u[t].x]==1)ans--;
		num[u[t].x]--;
	}
}
bool cmp(que x,que y)
{
	if(b[x.l]==b[y.l])
		if(b[x.r]==b[y.r])
			return x.t<y.t;
		else
			return b[x.r]<b[y.r];
	else
		return b[x.l]<b[y.l];
}
int main()
{
	cin>>n>>t;
	bs=round(pow(n*t,0.333));
	for(int i=1;i<=n;i++)
		cin>>a[i],b[i]=i/bs;
	for(int i=1;i<=t;i++)
		answer[i]=-1;
	while(t--)
	{
		cin>>ch;
		if(ch=='Q')
			cin>>q[++cnt].l,cin>>q[cnt].r,q[cnt].t=cnt;
		else
			cin>>u[++cnt].p,cin>>u[cnt].x;
	} 
	sort(q+1,q+cnt+1,cmp);
	t=0;
	for(int i=1;i<=cnt;i++)
	{
		if(!q[i].t)continue;
		while(l<q[i].l) del(l++);
		while(l>q[i].l) add(--l);
		while(r<q[i].r) add(++r);
		while(r>q[i].r) del(r--);
		while(t<q[i].t) upd(++t);
		while(t>q[i].t) und(t--);
		answer[q[i].t]=ans;
	} 
	for(int i=1;i<=t;i++)
		if(answer[i]!=-1)
			cout<<answer[i]<<endl; 
	
	return 0;
}