#include<bits/stdc++.h>
using namespace std;
#define N 133335
int n,tq,tr,m,siz,a[N],cnt[N],an[N];
struct q_
{
	int l,r,t,bh;
}q[N];
struct rep_
{
	int p,col;
}rep[N];
bool cmp(q_ a,q_ b)
{
	return a.l/siz!=b.l/siz?a.l/siz<b.l/siz:
	(a.r^b.r?(a.l/siz&1?a.r>b.r:a.r<b.r):a.t<b.t);
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	for(int i=1;i<=m;++i)
	{
		int x,y;
		char op[2];
		scanf("%s %d %d",&op,&x,&y);
		if(op[0]=='Q') q[++tq]=(q_){x,y,tr,tq};
		else rep[++tr]=(rep_){x,y};
	}
	siz=ceil(exp((log(n)+log(tr))/3));
	sort(q+1,q+tq+1,cmp);
	
	int l=1,r=0,tim=0,ans=0;
	for(int i=1;i<=tq;++i)
	{
		while(l<q[i].l) ans-=!--cnt[a[l++]];
		while(l>q[i].l) ans+=!cnt[a[--l]]++;
		while(r<q[i].r) ans+=!cnt[a[++r]]++;
		while(r>q[i].r) ans-=!--cnt[a[r--]];
		while(tim<q[i].t)
		{
			++tim;
			if(rep[tim].p>=l&&rep[tim].p<=r)
			{
				ans-=!--cnt[a[rep[tim].p]];
				ans+=!cnt[rep[tim].col]++;
			}
			swap(a[rep[tim].p],rep[tim].col);
		}
		while(tim>q[i].t)
		{
			if(rep[tim].p>=l&&rep[tim].p<=r)
			{
				ans-=!--cnt[a[rep[tim].p]];
				ans+=!cnt[rep[tim].col]++;
			}
			swap(a[rep[tim].p],rep[tim].col);
			--tim;
		}
		an[q[i].bh]=ans;
	}
	for(int i=1;i<=tq;++i) printf("%d\n",an[i]);
}