#include<bits/stdc++.h>
using namespace std;
int a[133334],ks[133334],suoyou[266667],ying[1000010];
struct node{
    int l,r;
    short zui_wan[166667],zui_zao[166667],num[166667];
}fk[366];
vector<int>v[366];
int pre[133334],mei_yong[133334],Next[133334];
struct kkksc03{
    int opt,l,r;
}Q[133334];
void Insert(int k,int x){
    fk[k].num[x]++;
}
void Del(int k,int x){
    fk[k].num[x]--;
}
int ask(int l,int r){
    int ll=ks[l],rr=ks[r],sum=0;
    if(ll==rr){
        for(int i=l;i<=r;i++){
            if(pre[i]<l)sum++;
        }
        return sum;
    }
    for(int i=l;i<=fk[ll].r;i++){
        if(pre[i]<l)sum++;
    }
    for(int i=fk[rr].l;i<=r;i++){
        if(pre[i]<l)sum++;
    }
    for(int i=ll+1;i<rr;i++){
        int pos=lower_bound(v[i].begin(),v[i].end(),l)-v[i].begin();
        sum+=pos;
    }
    return sum;
}
void geng(int x){
    int k=ks[x];
    for(int i=fk[k].l;i<=fk[k].r;i++){
        fk[k].zui_wan[a[i]]=i;
    }
    for(int i=fk[k].r;i>=fk[k].l;i--){
        fk[k].zui_zao[a[i]]=i;
    }
    v[k].clear();
    for(int i=fk[k].l;i<=fk[k].r;i++){
        v[k].push_back(pre[i]);
    }
    sort(v[k].begin(),v[k].end());
}
int n,m,len,cnt;
void change(int x,int y){
    if(a[x]==y)return;
    int ll=ks[x];
    Del(ll,a[x]);
    if(Next[x])pre[Next[x]]=pre[x],geng(Next[x]);
    if(pre[x])Next[pre[x]]=Next[x];
    bool f=1;
    for(int i=x-1;i>=fk[ll].l;i--){
        if(a[i]==y){pre[x]=i,f=0;break;}
    }
    if(f){
        for(int i=ll-1;i>=1;i--){
            if(fk[i].num[y]){
                pre[x]=fk[i].zui_wan[y],f=0;
                break;
            }
        }
        if(f)pre[x]=0;
    }
    f=1;
    for(int i=x+1;i<=fk[ll].r;i++){
        if(a[i]==y){Next[x]=i,f=0;break;}
    }
    if(f){
        for(int i=ll+1;i<=cnt;i++){
            if(fk[i].num[y]){
                Next[x]=fk[i].zui_zao[y],f=0;
                break;
            }
        }
        if(f)Next[x]=0;
    }
    if(pre[x])Next[pre[x]]=x;
    if(Next[x])pre[Next[x]]=x,geng(Next[x]);
    a[x]=y;
    Insert(ll,y);
    geng(x);
    // for(int i=1;i<=n;i++){
    //     cerr<<pre[i]<<" ";
    // }
    // cerr<<"\n";
    // for(int i=1;i<=n;i++){
    //     cerr<<Next[i]<<" ";
    // }
    // cerr<<"\n";
//    memset(mei_yong,0,sizeof(mei_yong));
//    for(int i=1;i<=n;i++){
//        pre[i]=mei_yong[a[i]];
//        mei_yong[a[i]]=i;
//    }
//    for(int i=1;i<=cnt;i++){
//    	geng(fk[i].l);
//	}
}

int main(){
    int tot=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        suoyou[++tot]=a[i];
    }
    for(int i=1;i<=m;i++){
        char ch;
        cin>>ch>>Q[i].l>>Q[i].r;
        if(ch=='Q')Q[i].opt=1;
        else Q[i].opt=2,suoyou[++tot]=Q[i].r;
    }
    sort(suoyou+1,suoyou+tot+1);
    int quc=unique(suoyou+1,suoyou+tot+1)-suoyou-1;
    for(int i=1;i<=quc;i++){
        ying[suoyou[i]]=i;
    }
    for(int i=1;i<=n;i++){
        a[i]=ying[a[i]];
        pre[i]=mei_yong[a[i]];
        mei_yong[a[i]]=i;
    }
    memset(mei_yong,0,sizeof(mei_yong));
    for(int i=n;i>=1;i--){
        Next[i]=mei_yong[a[i]];
        mei_yong[a[i]]=i;
    }
    len=sqrt(n);
    cnt=0;
    for(int i=1;i<=n;i++){
        ks[i]=(i-1)/len+1;
        Insert(ks[i],a[i]);
        fk[ks[i]].zui_wan[a[i]]=i;
        v[ks[i]].push_back(pre[i]);
        if((i-1)%len==0){
            fk[++cnt].l=i;
        }
        if(i%len==0){
            fk[cnt].r=i;
        }
    }
    for(int i=n;i>=1;i--){
        fk[ks[i]].zui_zao[a[i]]=i;
    }
    fk[cnt].r=n;
    for(int i=1;i<=cnt;i++)sort(v[i].begin(),v[i].end());
    for(int i=1;i<=m;i++){
        if(Q[i].opt==1){
            cout<<ask(Q[i].l,Q[i].r)<<"\n";
        }
        else{
            change(Q[i].l,ying[Q[i].r]);
        }
    }
    return 0;
}