#include <bits/stdc++.h>
using namespace std;
const int MAXN=500001;
const int MAXM=1000001;
int aa[MAXN],N,P0,P=0,sq,L,R,now,cnt[MAXM],ans[MAXN],rs[MAXN],ab[MAXN],T,X;
struct pr{
	int l,r,d,t;
}q[MAXN],q2[MAXN];
int f(int t)
{
	return t/sq;
}
bool operator<(pr a,pr b)
{
	if (f(a.l)==f(b.l)&&a.r==b.r) return a.t<b.t;
	if (f(a.l)!=f(b.l)) return f(a.l)<f(b.l);
		else if (f(a.l)%2==1) return a.r<b.r;
			return a.r>b.r;
}

int main()
{
	cin>>N;	cin>>P0;
	for (int i=1;i<=N;i++){
		scanf("%d",&aa[i]);
		ab[i]=aa[i];
	}
//	cout<<"N="<<N<<endl;
//	for (int i=1;i<=N;i++)
//		cout<<aa[i]<<' ';
//	cout<<endl;
	sq=pow(N,2.0/3.0)+1; 
	for (int i=1;i<=P0;i++){
		char ch;
		cin>>ch;
		if (ch=='Q'){ 
		P++;
		scanf("%d",&q[P].l);
		scanf("%d",&q[P].r);
		q[P].d=P;
		q[P].t=T;
		}
		else
		{
			int m,n;
			scanf("%d",&m);
			scanf("%d",&n);
			T++;
			q2[T].l=ab[m];
			q2[T].r=n;
			q2[T].t=T;
			q2[T].d=m;
			ab[m]=n;
		}
	}
	sort(q+1,q+P+1);
	L=1,R=0,X=0;
	for (int i=1;i<=P;i++){
//		cout<<i<<endl;
//		cout<<q[i].l<<' '<<q[i].r<<' '<<q[i].t<<endl;
		while(L < q[i].l) now -= !--cnt[aa[L++]];
		while(L > q[i].l) now += !cnt[aa[--L]]++;
		while(R < q[i].r) now += !cnt[aa[++R]]++;
		while(R > q[i].r) now -= !--cnt[aa[R--]];
//		cout<<L<<' '<<R<<endl;
//		for (int i=1;i<=6;i++)
//			cout<<cnt[i]<<' ';
//		cout<<endl;
		while (X>q[i].t){
			if (L<=q2[X].d&&q2[X].d<=R)
			{
				now -= !--cnt[q2[X].r];
				now += !cnt[q2[X].l]++;	
			}
				aa[q2[X].d]=q2[X].l;
			X--;
		}
		while (X<q[i].t){
			X++;
			if (L<=q2[X].d&&q2[X].d<=R)
			{
				now -= !--cnt[q2[X].l];
				now += !cnt[q2[X].r]++;
			}
				aa[q2[X].d]=q2[X].r;
		}
//		for (int i=1;i<=6;i++)
//			cout<<cnt[i]<<' ';
//		cout<<endl;
		ans[q[i].d]=now;
	}
	for (int i=1;i<=P;i++)
		cout<<ans[i]<<endl;
}
/*
6 7
1 1 1 1 1 1
Q 1 4
Q 2 5
R 1 2
Q 1 2
Q 2 6
R 6 6
Q 1 6
*/