#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct query
{
	int l,r;
	int id;
	int ch;
}q[1000010];
struct change
{
	int x;
	int val;
}c[1000010];
int belong[1000010];
bool cmp(query a,query b)
{
	if(a.l!=b.l) return belong[a.l]<belong[b.l];
	if(a.r!=b.r) return belong[a.r]<belong[b.r];
	return a.ch<b.ch;
}
int n,m;
int block;
int a[1000010];
int cnum,qnum;
int nl=1,nr,nc;
int b[1000010];
int now;
int ans[1000010];
inline void swap(int &x,int &y)
{
	int tmp=x;
	x=y;
	y=tmp;
}
inline void add(int x)
{
	if(++b[x]==1) now++;
}
inline void del(int x)
{
	if(--b[x]==0) now--;
}
inline void upd(int x,int i)
{
	if(c[x].x>=q[i].l&&c[x].x<=q[i].r)
	{
		del(a[c[x].x]);
		add(c[x].val);
	}
	swap(c[x].val,a[c[x].x]);
}
int main()
{
	scanf("%d%d",&n,&m);
	block=pow(n,0.666666);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		belong[i]=(i-1)/block+1;
	}
	for(int i=1;i<=m;i++)
	{
		char ch;
		scanf(" %c",&ch);
		if(ch=='Q')
		{
			qnum++;
			scanf("%d%d",&q[qnum].l,&q[qnum].r);
			q[qnum].id=qnum;
			q[qnum].ch=cnum;
		}
		else
		{
			++cnum;
			scanf("%d%d",&c[cnum].x,&c[cnum].val);
		}
	}
	sort(q+1,q+1+qnum,cmp);
	for(int i=1;i<=qnum;i++)
	{
		int L=q[i].l,R=q[i].r,C=q[i].ch;
		while(nl<L) del(a[nl++]);
		while(nl>L) add(a[--nl]);
		while(nr<R) add(a[++nr]);
		while(nr>R) del(a[nr--]);
		while(nc<C) upd(++nc,i);
		while(nc>C) upd(nc--,i);
		ans[q[i].id]=now;
	}
	for(int i=1;i<=qnum;i++) printf("%d\n",ans[i]);
	return 0;
}