#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
	int l,r,id,t;
}qq[1145141];
struct node1
{
	int pla,col;
}qr[1145141];
int cntq,cntr;
int n,m,a[1145141];
int size,belong[1145141];
int ans[1145141];
int cnt[1145141],l=1,r,t;
int now;
bool cmp(node x,node y)
{
	if(belong[x.l]==belong[y.l])
	{
		if(belong[x.r]==belong[y.r])
			return x.t<y.t;
		return x.r<y.r;
	}
	return belong[x.l]<belong[y.l];
}
void add(int x)
{
	if(!cnt[a[x]])
		++now;
	++cnt[a[x]];
}
void del(int x)
{
	--cnt[a[x]];
	if(!cnt[a[x]])
		--now;
}
void update(int x,int y)
{
	if(qq[x].l<=qr[y].pla&&qq[x].r>=qr[y].pla)
	{
		del(a[qr[y].pla]);
		add(qr[y].col);
	}
	swap(a[qr[y].pla],qr[y].col);
}
signed main()
{
	cin>>n>>m;
	size=pow(n,0.666);
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		belong[i]=i/size+1;
	for(int i=1;i<=m;i++)
	{
		char op;
		int x,y;
		cin>>op>>x>>y;
		if(op=='Q')
		{
			qq[++cntq].l=x;
			qq[cntq].r=y;
			qq[cntq].id=cntq;
			qq[cntq].t=cntr;
		}
		else
		{
			qr[++cntr].pla=x;
			qr[cntr].col=y;
		}
	}
	sort(qq+1,qq+cntq+1,cmp);
	for(int i=1;i<=cntq;i++)
	{
		while(l<qq[i].l)
			del(l++);
		while(l>qq[i].l)
			add(--l);
		while(r<qq[i].r)
			add(++r);
		while(r>qq[i].r)
			del(r--);
		while(t<qq[i].t)
			update(i,++t);
		while(t>qq[i].t)
			update(i,t--);
		ans[qq[i].id]=now;
	}
	for(int i=1;i<=cntq;i++)
		cout<<ans[i]<<endl;
}