#8 #9 #10 TLE

#include<bits/stdc++.h>
using namespace std;
const int maxn = 133335;

inline int read() {
    char c=getchar(),f=0;int t=0;
    for(;c<'0'||c>'9';c=getchar()) if(!(c^45)) f=1;
    for(;c>='0'&&c<='9';c=getchar()) t=(t<<1)+(t<<3)+(c^48);
    return f?-t:t;
}

inline void write(int x) {
    static int t[25];int tp=0;
    if(x==0) return(void)(putchar('0'));else if(x<0) putchar('-'),x=-x;
    while(x) t[tp++]=x%10,x/=10;
    while(tp--) putchar(t[tp]+48);
}

int n, m, a[maxn],t[1000005],bel[maxn],get_ans[maxn];
int cnt_a, cnt_q, ans;
struct que{
    int l, r, pre, id;
    inline bool operator < (const que & a) {
        return bel[l] == bel[a.l] ? (r == a.r ? pre < a.pre : r < a.r) : l < a.l;
    }
} q[maxn];
struct prefix {
    int poi, k;
} fix[maxn];

inline void doit(int now,int i) {
    if(fix[now].poi <= q[i].r && fix[now].poi >= q[i].l) {
        if(--t[a[fix[now].poi]] == 0)
            ans--;
        if(++t[fix[now].k] == 1)
            ans++;
    }
    swap(fix[now].k, a[fix[now].poi]);
}

signed main() {
    n = read(), m = read();
    int len = sqrt(n);
    for (int i = 1; i <= n; ++i)
        a[i] = read(), bel[i] = (i - 1) / len + 1;
    for (int i = 1, l, r; i <= m; ++i) {
        char opt[5];
        scanf("%s", opt);
        l = read(), r = read();
        if(opt[0] == 'Q') 
            q[++cnt_q] = (que){l, r, cnt_a, cnt_q};
        else
            fix[++cnt_a] = (prefix){l,r};
    }

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

    for (int i = 1, l = 1, r = 0, T = 0; i <= cnt_q; ++i)
    {
        while(r < q[i].r)
            if(++t[a[++r]] == 1)
                ans++;
        while(r > q[i].r)
            if(--t[a[r--]] == 0)
                ans--;
        while(l < q[i].l)
            if(--t[a[l++]] == 0)
                ans--;
        while(l > q[i].l)
            if(++t[a[--l]] == 1)
                ans++;
        while(T < q[i].pre)
            doit(++T, i);
        while(T > q[i].pre)
            doit(T--, i);
        get_ans[q[i].id] = ans;
    }

    for (int i = 1; i <= cnt_q;++ i) {
        cout << get_ans[i] << endl;
    }
    return 0;
}