#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    register int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
int pos[10000009], ans[10000009], a[10000009], cnt[10000009], cx, tt;
int n, m;
int sum;
struct node
{
    int l, r, k, t;
} cz1[10000009];
struct u
{
    int wz, z, t;
} cz2[10000009];
// bool cmp(node a, node b)
// {
//     return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];
// }

bool cmp(const node x, const node y)
{
    if (pos[x.l] != pos[y.l])
    {
        return x.l < y.l;
    }
    if (pos[x.r] != pos[y.r])
    {
        return x.r < y.r;
    }
    return x.t < y.t;
}
void jia(int x)
{
    cnt[x]++;
    if (cnt[x] - 1 == 0)
    {
        sum++;
    }
}
void shan(int x)
{
    cnt[x]--;
    if (cnt[x] == 0)
    {
        sum--;
    }
}
signed main()
{
    n = read();
    m = read();
    int len = pow(1.0 * n, 2.0 / 3.0);;
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
        pos[i] = i / len;
    }
    for (int i = 1; i <= m; i++)
    {
        char opt;
        opt = getchar();
        if (opt == 'Q')
        {
            cz1[++cx].l = read();
            cz1[cx].r = read();
            cz1[cx].k = cx;
            cz1[cx].t = tt;
        }
        else
        {
            cz2[++tt].wz = read();
            cz2[tt].z = read();
        }
    }
    sort(cz1 + 1, cz1 + cx + 1, cmp);
    int L = 1, R = 0, now = 0;
    for (int i = 1; i <= cx; i++)
    {
        while (cz1[i].l > L)
        {
            shan(a[L++]);
        }
        while (cz1[i].l < L)
        {
            jia(a[--L]);
        }
        while (cz1[i].r > R)
        {
            jia(a[++R]);
        }
        while (cz1[i].r < R)
        {
            shan(a[R--]);
        }
        while (now < cz1[i].t)
        {
            int v = cz2[++now].wz;
            if (v >= L && v <= R)
            {
                shan(a[v]);
                jia(cz2[now].z);
            }
            swap(a[v], cz2[now].z);
        }
        while (now > cz1[i].t)
        {
            int v = cz2[now].wz;
            if (v >= L && v <= R)
            {
                shan(a[v]);
                jia(cz2[now].z);
            }
            swap(a[v], cz2[now--].z);
        }
        ans[cz1[i].k] = sum;
    }
    for (int i = 1; i <= cx; i++)
    {
        printf("%d\n", ans[i]);
    }
    return 0;
}