#include<bits/stdc++.h>
using namespace std;
const int N= 2*1e6+10;
#define _ =read()
inline int read(){ 
    int r=0,W=1; 
    char ch=getchar(); 
    while(ch>'9'||ch<'0') { if(ch=='-') W=-1; ch=getchar();} 
    while(ch>='0'&&ch<='9') { r=r*10+ch-'0'; ch=getchar();} 
    return r*W;
} 

int n;
int m;
int now;
int tot;
int cnt;

int a[N];
int ton[N];
int ans[N];
int belong[N];
struct ss {
    int l;
    int r;
    int id;
    int pr;
}Q[N];
struct S{
    int pos;
    int k;
}C[N];
void add(int x){
    if(ton[a[x]]==0) now++;
    ton[a[x]] ++;
}
void de(int x){
    ton[a[x]]--;
    if(ton[a[x]]==0) now--;
}
bool comp(ss a,ss b){

return belong[a.l] == belong[b.l] ? ( belong[a.r] == belong[b.r] ? a.pr < b.pr : a.r< b.r ): a.l < b.l;
}
void Swap(int &x,int &y){
    int z;
    z=x;
    x=y;
    y=z;
}
void chenge(int kk,int i){
    if(C[kk].pos>=Q[i].l&&C[kk].pos<=Q[i].r){
        --ton[a[C[kk].pos]];
        if(ton[a[C[kk].pos]]==0) now--;
        ++ton[C[kk].k];
        if(ton[C[kk].k]==1) now++;
    }
    Swap(C[kk].k,a[C[kk].pos]);
}
signed main()
{
	   n _;
    m _;
    int base=pow(n, 0.6666666666);//这就对了，看得题解不明白 
    //int base=sqrt(n/5*3);/sqrt(n)/sqrt(2*n/3)   T 了 4个
    for(int i=1;i<=n;i++){
        a[i] _;
    }
    for(int i=1;i<=m;i++){
        char Opt[5];
       scanf("%s",Opt);
        if(Opt[0]=='Q'){
            Q[++cnt].l _;
            Q[cnt].r _;
            Q[cnt].id=cnt;
            Q[cnt].pr=tot;
        }
        if(Opt[0]=='R') {
            C[++tot].pos _;
            C[tot].k _;
        }
    }
    for(int i = 1; i <= n; i++) belong[i] = i/base + 1;
    sort(Q+1,Q+cnt+1,comp);
    tot=0;
    int l=1;
    int r=0;

    for(int i=1;i<=cnt;i++){
while(Q[i].l>l){
            de(l++);
        }
        while(Q[i].l<l){
            add(--l);
        }

        while(Q[i].r>r){
            add(++r);
        }

        while(Q[i].r<r){
            de(r--);
        }
        while(tot<Q[i].pr) chenge(++tot,i);
        while(tot>Q[i].pr) chenge(tot--,i);
        ans[Q[i].id]=now;
    }

    for(int i=1;i<=cnt;i++){
        printf("%d\n",ans[i]);  
    }
    return 0;
}

球助