#include <bits/stdc++.h>

#define N 1000006

#define setIO(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

using namespace std;

int n,m,ans,B,cnt,tot,now;

int a[N],tim[N],output[N];

struct query

{

    int l,r,t,id;

    bool operator<(query b) const

    {

        return l/B==b.l/B?(r/B==b.r/B?t<b.t:r<b.r):l<b.l;

    }

}q[N];

struct change

{

    int p,col;

}c[N];

void add(int x)

{

    if(tim[x]==0) ++ans;

    ++tim[x];

}

void del(int x)

{

    if(tim[x]==1) --ans;

    --tim[x];

}

void work(int x,int d)

{

    // 需要进行变动

    if(c[d].p>=q[x].l&&c[d].p<=q[x].r) del(a[c[d].p]), add(c[d].col);

    swap(c[d].col, a[c[d].p]);

}

int main()

{

    // setIO("input");

    int i,j,l=2,r=1;

    scanf("%d%d",&n,&m);

    B=pow(n,0.6666);

    for(i=1;i<=n;++i) scanf("%d",&a[i]);

    for(i=1;i<=m;++i)

    {

        char op[2];

        scanf("%s",op);

        if(op[0]=='Q')

        {

            ++cnt;

            scanf("%d%d",&q[cnt].l,&q[cnt].r);

            q[cnt].id=cnt;

            q[cnt].t=tot;

        }

        else

        {

            ++tot;

            scanf("%d%d",&c[tot].p,&c[tot].col);

        }

    }

    sort(q+1,q+1+cnt);

    for(i=1;i<=cnt;++i)

    {

        for(;l>q[i].l;) add(a[--l]);

        for(;r<q[i].r;) add(a[++r]);

        for(;l<q[i].l;) del(a[l++]);

        for(;r>q[i].r;) del(a[r--]);

        for(;now<q[i].t;) work(i, ++now);

        for(;now>q[i].t;) work(i, now--);

        output[q[i].id]=ans;

    }

    for(i=1;i<=cnt;++i) printf("%d\n",output[i]);

    return 0;

}