#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=150500,maxc=1001000;
struct query{
	int l,r,time,id; 
}q[maxn]; 
struct change{
	int pos,color; 
}c[maxn];
int n,m,cntq,cntc,sum,ans[maxn],bel[maxn],cnt[maxc],a[maxn];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
bool cmp(query a,query b){
    if(a.l!=b.l) return bel[a.l]<bel[b.l];
    if(a.r!=b.r) return bel[a.r]<bel[b.r];
    return a.time<b.time;
}
void add(int pos){
	if(!cnt[a[pos]]) sum++;
	cnt[a[pos]]++; 
}
void del(int pos){
	cnt[a[pos]]--;
	if(!cnt[a[pos]]) sum--;
}
int main(){
	n=read();
	m=read();
	int size=sqrt(sqrt(n)),num=ceil((double)n/size);
	for(int i=1;i<=num;i++)
	  for(int j=(i-1)*size;j<=i*size;j++) bel[j]=i;
	for(int i=1;i<=n;i++) a[i]=read();
	
	for(int i=1;i<=m;i++){
		char opt[11];
		scanf("%s",opt+1);
		if(opt[1]=='Q'){
			++cntq;
			q[cntq].l=read();
			q[cntq].r=read();
//			scanf("%d%d",&q[cntq].l,&q[cntq].r);
			q[cntq].id=cntq;
			q[cntq].time=cntc;
		}
		else{
			++cntc;
			c[cntc].pos=read();
			c[cntc].color=read();
//			scanf("%d%d",&c[cntc].pos,&c[cntc].color);
		}
	}
	sort(q+1,q+1+cntq,cmp);
	
	int l=1,r=0,time=0;
	for(int i=1;i<=cntq;i++){
		int ql=q[i].l,qr=q[i].r,qt=q[i].time;
		while(l<ql) del(l++);
		while(ql<l) add(--l);
		while(r<qr) add(++r);
		while(qr<r) del(r--);
		while(time<qt){
			time++;
			int pos=c[time].pos,color=c[time].color;
			if(ql<=pos&&pos<=qr){
				cnt[a[pos]]--;
				if(!cnt[a[pos]]) sum--;
				if(!cnt[c[time].color]) sum++; 
				cnt[c[time].color]++;
			}
			swap(a[pos],c[time].color);
		}
		while(qt<time){
			int pos=c[time].pos,color=c[time].color;
			if(ql<=pos&&pos<=qr){
				cnt[a[pos]]--;
				if(!cnt[a[pos]]) sum--;
				if(!cnt[c[time].color]) sum++; 
				cnt[c[time].color]++;
			}
			swap(a[pos],c[time].color);
		}
/*		printf("%d %d %d %d\n",ql,qr,qt,sum);*/
		ans[q[i].id]=sum;
	}
	for(int i=1;i<=cntq;i++) printf("%d\n",ans[i]);
	return 0; 
}