#include<bits/stdc++.h>

typedef long long LL;

using namespace std;

const int maxn = 50010;

int n,m,sqr,totc=0,totq=0;

int pos[maxn]={},las[maxn]={},ans[maxn]={},cnt[1000010]={},col[maxn]={};

char ch[2];

struct C{int x,v,la;}c[maxn];

struct Q{int l,r,k,id;}q[maxn];

inline bool cmd(Q a, Q b){

	if(a.l==b.l){

		if(a.r==b.r)return a.k<b.k;

		return a.r<b.r;

	}

	return a.l<b.l;

}

int main(){

	scanf("%d%d",&n,&m);sqr=pow((double)n,2.0/3.0);

	for(int i=1;i<=n;++i){scanf("%d",&col[i]);las[i]=col[i];}

	for(int i=1;i<=n;++i)pos[i]=(i-1)/sqr+1;

	for(int i=1;i<=m;++i){

		int x,y;scanf("%s%d%d",ch,&x,&y);

		if(ch[0]=='Q'){ q[++totq].l = x; q[totq].r = y; q[totq].id = totq; q[totq].k = totc; }

		else{ c[++totc].x = x; c[totc].v = y; c[totc].la = las[x]; las[x] = y; }

	}

	sort(q+1,q+totq+1,cmd);

	int tk=0,tl=1,tr=0,tnow=0;

	for(int i=1;i<=totq;++i){

		while(tk<q[i].k){

			++tk;

			if(tl<=c[tk].x&&c[tk].x<=tr){

				--cnt[c[tk].la];++cnt[c[tk].v];

				if(cnt[c[tk].la]==0)--tnow;

				if(cnt[c[tk].v]==1)++tnow;

			}

			col[c[tk].x]=c[tk].v;

		}

		while(tk>q[i].k){

			if(tl<=c[tk].x&&c[tk].x<=tr){

				++cnt[c[tk].la];--cnt[c[tk].v];

				if(cnt[c[tk].la]==1)++tnow;

				if(cnt[c[tk].v]==0)--tnow;

			}

			col[c[tk].x]=c[tk].la;

			--tk;

		}

		while(tl<q[i].l){if(cnt[col[tl]]==1)--tnow;--cnt[col[tl]];++tl;}

		while(tl>q[i].l){--tl;++cnt[col[tl]];if(cnt[col[tl]]==1)++tnow;}

		while(tr<q[i].r){++tr;++cnt[col[tr]];if(cnt[col[tr]]==1)++tnow;}

		while(tr>q[i].r){if(cnt[col[tr]]==1)--tnow;--cnt[col[tr]];--tr;}

		ans[q[i].id]=tnow;

	}

	for(int i=1;i<=totq;++i)printf("%d\n",ans[i]);

	return 0;

}