#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7+5;
int n , m , T , cnt , a[maxn] , bel[maxn] , t[maxn] , ans[maxn] , res , B , L , R;
struct qu{int l , r , ti , id;}q[maxn];
struct cg{int p , x;}c[maxn];
bool cmp(qu x , qu y)
{
	if (bel[x.l] ^ bel[y.l]) return x.l < y.l;
	if (x.r ^ y.r) return bel[x.l] & 1 ? x.r < y.r : x.r > y.r;
	return x.ti < y.ti;
}
void Add(int x){res+=t[a[x]]++==0;}
void Del(int x){res-=--t[a[x]]==0;}
void Change(int now , int l , int r)
{
	int p = c[now].p , tmp = a[p];
	if (p >= l && p <= r) Del(p),a[p]=c[now].x,Add(p);
	a[p]=c[now].x;
	c[now].x=tmp;
	return;
}
int Query(int l , int r , int t)
{
	while(l < L)Add(--L);
	while(r > R)Add(++R);
	while(l > L)Del(L++);
	while(r < R)Del(R--);
	while(T > t)Change(T-- , l , r);
	while(T < t)Change(++T , l , r);
//	cout << res << endl;
//	cout << l << " " << r << " " << t << " " << res << endl;
	return res;
}
int main ()
{
	scanf("%d%d" , &n , &m);
	for (int i = 1; i <= n; i++)scanf("%d" , &a[i]);
	T=1;
	for (int i = 1; i <= m; i++)
	{
		char op;
		scanf(" %c" , &op);
		if (op == 'Q')cnt++,scanf("%d%d" , &q[cnt].l , &q[cnt].r),q[cnt].id=cnt,q[cnt].ti=T;
		else T++,scanf("%d%d" , &c[T].p , &c[T].x);
	}
//	B = max(cbrt(1.0 * n * n * T / m) , 1.0);
	B = pow(n , 0.6666);
	for (int i = 1; i <= n; i++)bel[i]=(i - 1)/B+1;
	sort(q + 1 , q + cnt + 1 , cmp);
	L=R=T=t[a[1]]=1;
	res=1;
	for (int i = 1; i <= cnt; i++)
	{
		ans[q[i].id]=Query(q[i].l , q[i].r , q[i].ti);
	}
	for (int i = 1; i <= cnt; i++)printf("%d\n" , ans[i]);
	return 0;
}