#include <bits/stdc++.h>

using namespace std;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch-'0'); ch=getchar();}
    return x*f;
}

const int N=2e5;

struct node1{
    int l,r,k,pre;
}q[N];

struct node2{
    int pos,val;
}change[N];

int n,m,cnt1,cnt2,ANS=0,block;
int a[N],bl[N],cnt[N],ans[N];

bool cmp(node1 x,node1 y)
{
    if(x.l!=y.l) return bl[x.l]<bl[y.l];
    if(x.r!=y.r) return bl[x.r]<bl[y.r];
    return x.pre < y.pre;
}

inline void add(int x)
{
    if(++cnt[a[x]] == 1) ANS++;
}

inline void del(int x)
{
    if(--cnt[a[x]] == 0) ANS--;
}

void solve(int now,int i)
{
    if(change[now].pos>=q[i].l&&change[now].pos<=q[i].r)
    {
        if( --cnt[a[change[now].pos]] ==0) ANS--;
        if( ++cnt[change[now].val] == 1) ANS++; 
    }
    swap(change[now].val,a[change[now].pos]);
}

int main()
{
    n=read(); m=read();
    block=n*(2.0/3.0);
    for(int i=1 ;i<=n ;i++ )
    {
        a[i]=read();
        bl[i]=(i-1)/block+1;
    }
    for(int i=1 ;i<=m ;i++ )
    {
        char ch;
        cin >> ch;
        if(ch=='Q')
        {
            q[++cnt1].l=read();
            q[cnt1].r=read();
            q[cnt1].k=cnt2;
            q[cnt1].pre=cnt1;
        }
        else if(ch=='R')
        {
            change[++cnt2].pos=read();
            change[cnt2].val=read();
        }
    }
    sort(q+1,q+cnt1+1,cmp);
    int L=1,R=0,now=0;
    for(int i=1 ;i<=cnt1 ;i++ )
    {
        while(L<q[i].l) add(L++);
        while(R>q[i].r) add(R--);
        while(L>q[i].l) del(--L);
        while(R<q[i].r) del(++R);
        while(now<q[i].pre) solve(++now,i);
        while(now>q[i].pre) solve(now--,i);
        ans[q[i].k]=ANS;
    }
    for(int i=1 ;i<=cnt1 ;i++ ) printf("%d\n" ,ans[i]);
    return 0;
}