#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define rint register int 
using namespace std;
const int maxn=2000000+5;
int n,Q;
int col[maxn],belong[maxn],cnt,cntq,cntu,ans,aans[maxn];
//带修改莫队
int Count[maxn];//Count[i]颜色i出现的次数 
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){
         if(c=='-')f=-1;c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^'0');c=getchar();
    }return f*x;
}
void print(int x){
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
struct block{
    int l,r;
}p[maxn];
struct que{
    int l,r,id,tim;
	//第id次询问前一次更新
}q[maxn];
struct upd{
	int pos,val;
}u[maxn];
bool cmp(que x,que y){
    return belong[x.l] == belong[y.l] ? belong[x.r] == belong[y.r] ? x.tim<y.tim : x.r<y.r : x.l<y.l;
}
void add(int pos){
	if(!Count[col[pos]])ans++;
	Count[col[pos]]++;
}
void del(int pos){
	Count[col[pos]]--;
	if(!Count[col[pos]])ans--;
}
void work(){
     n=read();Q=read();
     for(rint i=1;i<=n;++i){
         col[i]=read();
     }
	 int block=pow(n,0.6666666666);
	 for(int i=1;i<=n;++i){
		 belong[i]=i/block;
	 }
	 for(rint i=1;i<=Q;++i){
	 	char c;scanf(" %c",&c);
	 	if(c=='Q'){
	 		int l=read(),r=read();
	 		q[++cntq].l=l,q[cntq].r=r,q[cntq].id=cntq,q[cntq].tim=cntu;
		}
		else{
		    int pos=read(),cl=read();
		    u[++cntu].pos=pos,u[cntu].val=cl;
		} 
	 }
	 sort(q+1,q+cntq+1,cmp);
	 int l=1,r=0,t=0;ans=0;
	 for(rint i=1;i<=cntq;++i){
	 	 //注意l++ ++l 
	 	 while(l>q[i].l)add(--l);
		 while(l<q[i].l)del(l++);
		 while(r>q[i].r)del(r--);
	 	 while(r<q[i].r)add(++r);
	 	 while(t<q[i].tim){//没有更新的更新
			if(q[i].l<=u[++t].pos && u[t].pos<=q[i].r){
				del(u[t].pos);
				if(!Count[u[t].val])ans++;
				Count[u[t].val]++;
			}
			swap(u[t].val,col[u[t].pos]);
		 }
		 while(t>q[i].tim){//把改过的改回来 
		    if(q[i].l<=u[t].pos && u[t].pos<=q[i].r){//否则对答案没有影响
				del(u[t].pos);//此时col中是更新后的颜色，q中是原来的颜色
				if(!Count[u[t].val])ans++;
				Count[u[t].val]++;
			}
			swap(u[t].val,col[u[t--].pos]);
		 }
		 aans[q[i].id]=ans; 
	 }
	 for(rint i=1;i<=cntq;++i){ 
	 	 print(aans[i]);putchar('\n');
	 }
}
int main(){
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	work();
    return 0;
}