# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi 3.1415926535

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

struct Node{int l, r; bool flag;}node[N];

int a[N], vis[N<<], to[N], sz, n;

int root[N], ls[N*], rs[N*], s[N*];

VI v;

set<int>mt[N<<];

set<int>::iterator it;

void update(int l, int r, int x, int &y, int z, int val){

    y=++sz;

    s[y]=s[x]+val;

    if (l==r) return ;

    ls[y]=ls[x]; rs[y]=rs[x];

    int mid=(l+r)>>;

    if (z<=mid) update(l,mid,ls[x],ls[y],z,val);

    else update(mid+,r,rs[x],rs[y],z,val);

}

int query(int l, int r, int x, int L){

    if (r<L) return ;

    if (l>=L) return s[x];

    int mid=(l+r)>>;

    return query(l,mid,ls[x],L)+query(mid+,r,rs[x],L);

}

void add(int x, int y, int val){

    for (int i=x; i<=n; i+=lowbit(i)) update(,n+,root[i],root[i],y,val);

}

int sum(int x, int val){

    int res=;

    for (int i=x; i; i-=lowbit(i)) res+=query(,n+,root[i],val);

    return res;

}

int main ()

{

    int m, tmp;

    char flag[];

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

    FOR(i,,n) scanf("%d",a+i), v.pb(a[i]);

    FOR(i,,m) {

        scanf("%s%d%d",flag,&node[i].l,&node[i].r);

        if (flag[]=='Q') node[i].flag=true;

        else v.pb(node[i].r);

    }

    sort(v.begin(),v.end());

    int siz=unique(v.begin(),v.end())-v.begin();

    FOR(i,,n) {

        a[i]=lower_bound(v.begin(),v.begin()+siz,a[i])-v.begin()+;

        if (vis[a[i]]) to[vis[a[i]]]=i;

        vis[a[i]]=i;

        mt[a[i]].insert(i);

    }

    FOR(i,,n) if (!to[i]) to[i]=n+;

    FOR(i,,n) add(i,to[i],);

    FOR(i,,m) {

        if (node[i].flag) printf("%d\n",sum(node[i].r,node[i].r+)-sum(node[i].l-,node[i].r+));

        else {

            node[i].r=lower_bound(v.begin(),v.begin()+siz,node[i].r)-v.begin()+;

            it=mt[a[node[i].l]].lower_bound(node[i].l);

            ++it;

            if (it==mt[a[node[i].l]].end()) tmp=n+;

            else tmp=*it;

            add(node[i].l,tmp,-);

            --it;

            if (it!=mt[a[node[i].l]].begin()) --it, add(*it,node[i].l,-), add(*it,tmp,);

            mt[a[node[i].l]].erase(node[i].l);

            a[node[i].l]=node[i].r;

            it=mt[node[i].r].lower_bound(node[i].l);

            if (it==mt[node[i].r].end()) tmp=n+;

            else tmp=*it;

            add(node[i].l,tmp,);

            if (it!=mt[node[i].r].begin()) --it, add(*it,tmp,-), add(*it,node[i].l,);

            mt[node[i].r].insert(node[i].l);

        }

    }

    return ;

}