#include<bits/stdc++.h>
using namespace std;
const int N=133334;
const int V=1e6+5;
int n,m,a[N],cnt[V],tim=0,q1=0,b[N],temp=0,ans[N];
struct Query{
    int l,r,t,id;
    Query(){}
    Query(int _l,int _r,int _t,int _id):l(_l),r(_r),t(_t),id(_id){}
    bool operator < (const Query &p)const{
        return b[l]==b[p.l]?(b[r]==b[p.r]?t<p.t:b[r]<b[p.r]):b[l]<b[p.l];
    }  
}q[N];
struct Modi{
	int p,f;
	Modi(){}
	Modi(int _p,int _f):p(_p),f(_f){}
}modi[N];
void add(int x){
    cnt[x]++;
    if(cnt[x]==1) ++temp;
}
void del(int x){
   	cnt[x]--;
   	if(!cnt[x]) --temp;
}
void modify(int k,int i){
	if(modi[k].p>=q[i].l&&modi[k].p<=q[i].r){
		add(modi[k].f);
		del(a[modi[k].p]); 
	}
	swap(a[modi[k].p],modi[k].f);
}
int main(){
    scanf("%d%d",&n,&m);
  	int Size=cbrt(n*n);
    for(int i=1;i<=n;i++){
    	scanf("%d",&a[i]);
    	b[i]=(i-1)/Size+1;
    }
    for(int i=1;i<=m;i++){
    	char command[3];
    	int x,y;
    	scanf("%s",command);
    	scanf("%d%d",&x,&y); 
    	if(command[0]=='Q') ++q1,q[q1]=Query(x,y,tim,q1);
    	else ++tim,modi[tim]=Modi(x,y);
    }
    sort(q+1,q+q1+1);
    int l=1,r=0,t=0;
    for(int i=1;i<=q1;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) modify(++t,i);
        while(t>q[i].t) modify(t--,i);
        ans[q[i].id]=temp;
    }
    for(int i=1;i<=q1;i++) printf("%d\n",ans[i]);
    return 0;
}