#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#define ll long long
using namespace std;
const int N=1000010,M=133333;
struct MD1{int l,r,id,t;}ask[M];
struct MD2{int id,ne,old;}change[M];
int sum1,sum2;
int n,m,g;
int a[M];
int l=1,r,t; 
bool cmp(MD1 x,MD1 y)
{
	if(x.l/g!=y.l/g)return x.l<y.l;
	if(x.r/g!=y.r/g)return x.r<y.r;
	return x.t<y.t;
}
int sum;
int cnt[N],ans[M];
void add(int x)
{
	if(cnt[a[x]]==0)sum++;
	cnt[a[x]]++;
}
void del(int x)
{
	if(cnt[a[x]]==1)sum--;
	cnt[a[x]]--;
}
void modify(int x,int y,int t)
{
	if(x>=l&&x<=r)del(x);
	//cout<<x<<" "<<y<<endl; 
	a[x]=y;
	if(x>=l&&x<=r)add(x);
}
int main()
{
	scanf("%d%d",&n,&m);
	g=pow(n,5/3);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)
	{
		char op;
		int x,y;
		cin>>op;
		scanf("%d%d",&x,&y);
		if(op=='Q')
		{
			sum1++;
			ask[sum1].l=x;
			ask[sum1].r=y;
			ask[sum1].id=sum1;
			ask[sum1].t=sum2;
		}
		if(op=='R')
		{
			sum2++;
			change[sum2].id=x;
			change[sum2].ne=y;
			change[sum2].old=a[x];
			//a[x]=y;
		}
	}
	sort(ask+1,ask+1+sum1,cmp);
	for(int i=1;i<=sum1;i++)
	{
		int ql=ask[i].l,qr=ask[i].r,qi=ask[i].id,qt=ask[i].t;
		while(l<ql)del(l++);
		while(l>ql)add(--l);
		while(r<qr)add(++r);
		while(r>qr)del(r--);
		//cout<<i<<"1:"<<a[1]<<endl;
		//cout<<t<<" "<<qt<<endl; 
		while(t>qt)modify(change[t].id,change[t].old,t--);
		while(t<qt)modify(change[t].id,change[t].ne,++t);
		//cout<<i<<"2:"<<a[1]<<endl;
		ans[qi]=sum;
	}
	for(int i=1;i<=sum1;i++)printf("%d\n",ans[i]);
	return 0;
}