#include <bits/stdc++.h>
using namespace std;
const int N=10000005;
long long n,m,a[N],B,qm,um,b[N],nl=1,nr,now,js[N];
long long sum;
struct wasd{
    int l,r,sum,i;
    long long n;
}d[N];
struct node{
    int v,lv,w;
}op[N];
bool cmp(wasd x,wasd y){
    if(x.l/B!=y.l/B)return x.l<y.l;
    if(x.r/B!=y.r/B)return x.r<y.r;
    return x.sum<y.sum;
}
bool cmp1(wasd x,wasd y){
    return x.i<y.i;
}
void add(int u){
	if(!js[a[u]])sum++;
	js[a[u]]++;
}
void del(int u){
	js[a[u]]--;
	if(!js[a[u]])sum--;
}
void back(int x,int l,int r){
	int p=op[x].w;
    if(l<=p&&p<=r){
        del(x);
        a[p]=op[x].v;
        add(x);
    }else{
        a[p]=op[x].v;
    }
}
void past(int x,int l,int r){
    int p=op[x].w;
    if(l<=p&&p<=r){
        del(x);
        a[p]=op[x].lv;
        add(x);
    }else{
        a[p]=op[x].lv;
    }
}
long long Modui(int u,int l,int r){
    while(nl>l)add(--nl);
    while(nl<l)del(nl++);
    while(nr>r)del(nr--);
    while(nr<r)add(++nr);
    while(now<d[u].sum)back(++now,l,r);
    while(now>d[u].sum)past(now--,l,r);
    return sum;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
    B=pow(n,0.666);
    for(int i=1,l,r,p,c;i<=m;i++){
        char w;
        cin>>w;
        if(w=='Q'){
            cin>>l>>r;
            d[++qm].l=l,d[qm].r=r,d[qm].sum=um,d[qm].i=qm;
        }else{
            cin>>p>>c;
            op[++um].w=p,op[um].v=c,op[um].lv=b[p],b[p]=c;
        }
    }
    sort(d+1,d+1+qm,cmp);
    for(int i=1;i<=qm;i++)d[i].n=Modui(i,d[i].l,d[i].r);
    sort(d+1,d+1+qm,cmp1);
    for(int i=1;i<=qm;i++)cout<<d[i].n<<"\n";
    return 0;
}