#include <bits/stdc++.h>
using namespace std;
const int N = 1333333 + 10;
int belong[N], a[N], Qid, Cid, res[N], ans, cnt[N], cur;
int n, m, len, Tim[N], Pen[N], Col[N], pre[N];
int dl = 1, dr;
struct Node {
	int id, l, r, tim;
	friend bool operator < (Node x, Node y) {
		if (belong[x.l] != belong[y.l]) return belong[x.l] < belong[y.l];
		if (belong[x.r] != belong[y.r]) return belong[x.r] < belong[y.r];
		return x.id < y.id;
	}
} Ques[N];
void change_add(int cur) {
	if (Pen[cur] >= dl && Pen[cur] <= dr) {
		-- cnt[a[Pen[cur]]];
		if (!cnt[a[Pen[cur]]]) -- ans;
	}
	pre[cur] = a[Pen[cur]];
	a[Pen[cur]] = Col[cur];
	if (Pen[cur] >= dl && Pen[cur] <= dr) {
		if (!cnt[a[Pen[cur]]]) ++ ans;
		++ cnt[a[Pen[cur]]];
	}
}
void change_del(int cur) {
	if (Pen[cur] >= dl && Pen[cur] <= dr) {
		-- cnt[a[Pen[cur]]];
		if (!cnt[a[Pen[cur]]]) -- ans;
	}
	a[Pen[cur]] = pre[cur];
	if (Pen[cur] >= dl && Pen[cur] <= dr) {
		if (!cnt[a[Pen[cur]]]) ++ ans;
		++ cnt[a[Pen[cur]]];
	}
}
void tran(int t) {
	while (cur < Cid && Tim[cur + 1] <= t) change_add(++ cur);
	while (cur && Tim[cur] > t) change_del(cur --);
}
void add(int x) {
	if (!cnt[a[x]]) ++ ans;
	++ cnt[a[x]];
}
void del(int x) {
	-- cnt[a[x]];
	if (!cnt[a[x]]) -- ans;
}
int main() {
	cin >> n >> m; len = pow(n, 1.0 * 2 / 3);
	for (int i = 1; i <= n; ++ i) cin >> a[i];
	for (int i = 1; i <= m; ++ i) {
		char pos; int l, r; cin >> pos >> l >> r;
		if (pos == 'Q') {
			++ Qid;
			Ques[Qid] = {.id = Qid, .l = l, .r = r, .tim = i};
		}
		else {
			++ Cid;
			Tim[Cid] = i;
			Pen[Cid] = l;
			Col[Cid] = r;
		}
	} sort(Ques + 1, Ques + Qid + 1);
	for (int i = 1; i <= Qid; ++ i) {
		Node cur = Ques[i];
		tran(cur.tim);
		while(dl > Ques[i].l) add(-- dl);
		while (dr < Ques[i].r) add(++ dr);
		while (dl < Ques[i].l) del(dl ++);
		while (dr > Ques[i].r) del(dr --);
//		cout << cur.id << ' ' << ans << endl;
		res[cur.id] = ans;
	}
	for (int i = 1; i <= Qid; ++ i) cout << res[i] << endl;
	return 0;
}