#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int tot,n,m,len,cnt[N],a[N],B[N],qcnt,ccnt,ans[N];
struct node {
	int l,r,id,t;
	bool operator<(const node &u) const{
		if(B[u.l]==B[l]) {
			if(B[u.r]==B[r]) return t<u.t;
			return r<u.r;
		}
		return B[l]<B[u.l];
	}
}q[N];
struct change {
	int p,old,nw;
}c[N];
void Add(int x) {tot+=(++cnt[x]==1);}
void Del(int x) {tot-=(--cnt[x]==0);}

void modui() {
	sort(q+1,q+1+qcnt);
	int L=1,R=0,T=0;
	for(int i=1;i<=qcnt;i++) {
		while(R<q[i].r) Add(a[++R]);
		while(R>q[i].r) Del(a[R--]);
		while(L>q[i].l) Add(a[--L]);
		while(L<q[i].l) Del(a[L++]);
		while(T<q[i].t) {
			int x=c[++T].p;
			if(x>=L&&x<=R) Del(a[x]),Add(c[T].nw);
			a[x]=c[T].nw;
		}
		while(T>q[i].t) {
			int x=c[T].p;
			if(x>=L&&x<=R) Del(a[x]),Add(c[T].old);
			a[x]=c[T].old;
			--T;
		}
		ans[q[i].id]=tot;
	}
}
int main() {
	scanf("%d%d",&n,&m);
	len=pow(n,2/3.0);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),B[i]=(i-1)/len+1;
	for(int i=1;i<=m;i++) {
		char s[5];
		int x,y;
		scanf("%s%d%d",s,&x,&y);
		if(s[0]=='Q') ++qcnt,q[qcnt]=(node){x,y,qcnt,ccnt};
		else ++ccnt,c[ccnt]=(change){x,a[x],y};
	}
	modui();
	for(int i=1;i<=qcnt;i++) printf("%d\n",ans[i]);
	return 0;
}