#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <iomanip>
#define _fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(e) push_back(e)
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define endl '\n'

using namespace std;
using i64 = long long;
using PII = pair<int,int>;
const int INF = 0x3f3f3f3f;


int main()
{
    int n,m;const int N = 1e6+10;
    cin >> n >> m;
    int kn = pow(n,0.6666);
    vector<int> v(N),K(N),cnt(N);
    vector<array<int,4> > query = {{}};//l,r,time,id
    vector<array<int,2> > modify = {{}};//下标,值
    for(int i=1;i<=n;++i) cin >> v[i],K[i] = (i-1)/kn + 1;
    for(int i=1;i<=m;++i)
    {
        string s;int x,y;cin >> s >> x >> y;
        if(s == "Q") query.push_back({x,y,(int)modify.size() - 1,(int)query.size()});
        else modify.push_back({x,y});
    }
    sort(query.begin() + 1,query.end(),[&](auto x,auto y){
        if(K[x[0]] != K[y[0]]) return x[0] < y[0];
        if(K[x[1]] != K[y[1]]) return x[1] < y[1];
        return x[3] < y[3];
    });
    vector<int> ans(query.size());
    int l = 1,r = 0,val = 0,t = 0;//t为累计修改次数
    for(int i=1;i<query.size(); ++ i)
    {
        auto &e = query[i];
        int ql = e[0],qr = e[1],qt = e[2],id = e[3];
        auto add = [&](int x) -> void {
            if(!cnt[x]) val += 1;
            cnt[x] ++ ;
        };
        auto sub = [&](int x) -> void {
            cnt[x] -- ;
            if(!cnt[x]) val -=1;
        };
        auto time = [&](int x,int l,int r) -> void {
            int w = modify[x][1], id = modify[x][0];
            if(l <= id && id <= r)
            {
                sub(v[id]);
                add(w);
                // cnt[v[id]] -- ;
                // if(!cnt[v[id]]) val -- ;

                // if(!cnt[w]) val ++ ;
                // cnt[w] ++ ;
            }
            swap(v[id],w);
        };
        while (l > ql) add(v[--l]);
        while (r < qr) add(v[++r]);
        while (l < ql) sub(v[l++]);
        while (r > qr) sub(v[r--]);
        while (t < qt) time(++t, ql, qr);
        while (t > qt) time(t--, ql, qr);
        ans[id] = val;
    }
    for(int i=1;i<ans.size();++i) cout << ans[i] << endl;
    return 0;
}