#include <bits/stdc++.h>
#define int long long
#define maxn 5000005
using namespace std;
int n, m, a[maxn], t[maxn], ans, qtot, sqr, ctot, ansn[maxn];
struct node {
	int l, r, id, lt, cnt;
}Q[maxn << 1];
struct nod {
	int p, val;
}C[maxn << 1];
bool cmp(node a, node b) {
	if(a.l != b.l) return a.cnt < b.cnt;
	if(a.r != b.r) return a.cnt < b.cnt;
	return a.lt < b.lt;//TLE
	
//	if(a.cnt == b.cnt) return a.l < b.l;
//	if(a.cnt & 1) return a.r > b.r;
//	return a.r < b.r;//WA+TLE

//	if(a.cnt == b.cnt) return a.l < b.l;
//	if(a.cnt & 1) return a.r > b.r;
//	return a.lt < b.lt;//TLE
}
void ins(int p) {
	if(t[a[p]] ++ == 0) ans ++;
}
void del(int p) {
	if(-- t[a[p]] == 0) ans --;
}
void work(int x, int k) {
	if(Q[k].l <= C[x].p && C[x].p <= Q[k].r) {
		if(-- t[a[C[x].p]] == 0) ans --;
		if(t[C[x].val] ++ == 0) ans ++;
	}
	swap(C[x].val, a[C[x].p]);
}
signed main() {
	scanf("%lld%lld", &n, &m);
	sqr = pow(n, 0.666);
	for(int i = 1;i <= n;i++) scanf("%lld", &a[i]);
	for(int i = 1;i <= m;i++) {
		char p;
		cin >> p;
		if(p == 'Q') {
			++qtot;
			scanf("%lld%lld", &Q[qtot].l, &Q[qtot].r);
			Q[qtot].cnt = Q[qtot].l / sqr + (Q[qtot].l % sqr != 0);
			Q[qtot].id = qtot;
			Q[qtot].lt = ctot; 
		}
		else {
			++ctot;
			scanf("%lld%lld", &C[ctot].p, &C[ctot].val);
		}
		
	}
	
	sort(Q + 1, Q + 1 + qtot, cmp);
	int l = 1, r = 0, now = 0;
	for(int i = 1;i <= qtot;i++) {
		while(l > Q[i].l) ins(-- l);
		while(r < Q[i].r) ins(++ r);
		while(l < Q[i].l) del(l ++);
		while(r > Q[i].r) del(r --);
		while(now < Q[i].lt) work(++ now, i);
		while(now > Q[i].lt) work(now --, i);
		ansn[Q[i].id] = ans;
	}
	for(int i = 1;i <= qtot;i++) printf("%lld\n", ansn[i]);
}