#include<bits/stdc++.h>
using namespace std;
int s,l,r,n,m,a[1000010];
int cnt[1000010];
struct p
{
	int l,r,id,pre;
} ask[1000010];
struct ch
{
	int pos,v;
}q[1000010];
#define blo(i) (i-1)/s+1
int ans[1000010];
int now=0;
void add(int x){if(++cnt[a[x]]==1) now++;}
void del(int x){if(--cnt[a[x]]==0) now--;}
bool cmp(p m,p n)
{
	if(blo(m.l)!=blo(n.l)) return blo(m.l)<blo(n.l);
	if(m.r!=n.r) return m.r<n.r;
	return m.pre<n.pre;
}
void change(int x,int y)
{
	if(q[x].pos>=ask[y].l&&q[x].pos<=ask[y].r)
	{
		if(--cnt[a[q[x].pos]]==0) now--;
		if(++cnt[q[x].v]==1) now++;
	}
	swap(q[x].v,a[q[x].pos]);
}
void solve()
{
	//do something
	cin>>n>>m;
	s=pow(n,0.75);
	for(int i=1;i<=n;i++) cin>>a[i];
	int cnt1=0,cnt2=0;
	char ss[10];
	for(int i=1;i<=m;i++) 
	{
		//string s;
		cin>>ss+1;
		if(ss[1]=='Q')
		{
			cnt1++;
			cin>>ask[cnt1].l>>ask[cnt1].r,ask[cnt1].id=cnt1,ask[cnt1].pre=cnt2;
		}
		else
		{
			cnt2++;
			cin>>q[cnt2].pos>>q[cnt2].v;
		}
	}
	sort(ask+1,ask+cnt1+1,cmp);
	int nowc=0;
	l=1;r=0;
	for(int i=1;i<=cnt1;i++)
	{
		while(l<ask[i].l) del(l++);
		while(l>ask[i].l) add(--l);
		while(r<ask[i].r) add(++r);
		while(r>ask[i].r) del(r--);
		while(nowc<ask[i].pre) change(++nowc,i);
		while(nowc>ask[i].pre) change(nowc--,i);
		ans[ask[i].id]=now;
	}
	for(int i=1;i<=cnt1;i++) cout<<ans[i]<<'\n';
}
void multi()
{
	//rd(tst);
	int tst=1;
	while(tst--)
	{
		solve();
	}
	//pcc();
}
signed main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	multi();
}
// POWERED BY WITHERS
// THINK ONCE, CODE TWICE
/*things to check
1.  int overflow or long long memory need
2.  recursion/array/binary search/dp/loop bounds
3.  precision
4.  special cases(n=1,bounds)
5.  delete debug statements
6.  initialize(especially multi-tests)
7.  = or == , n or m ,++ or -- , i or j , > or >= , < or <= , - or =
8.  keep it simple and stupid
9.  do not delete, use // instead
10. operator priority
11. is there anything extra to output?
12. if you don't know where the bug is , try to clear some parts of the code
 and check each part seperately.
13. ...
*/
 
/* something to think about
1. greedy? dp? searching? dp with matrix/ segment tree? binary search?
2. If contains "not", why not 正难则反 or few affect?
*/