#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 1e6 + 10;

struct modify {
	int p, c;
	modify() = default;
	modify(int p, int c): p(p), c(c) {}
};

struct query {
	int l, r, t, id;
	query() = default;
	query(int l, int r, int t, int id): l(l), r(r), t(t), id(id) {}
};

int n, c, m, t, s, l = 1, r, k, cur;
int a[maxn], b[maxn];
query q[maxn];
modify f[maxn][2];
int ans[maxn];
int cnt[maxn];

void add(int p) {
	if (!cnt[a[p]]) ++cur;
	cnt[a[p]]++;
}

void rem(int p) {
	cnt[a[p]]--;
	if (!cnt[a[p]]) --cur;
}

void mdf(int p, int id) {
	if (l <= f[p][id].p && f[p][id].p <= r) {
		add(f[p][id].c);
		rem(a[f[p][id].p]);
	}
	a[f[p][id].p] = f[p][id].c;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> c;
	for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
	for (int i = 1; i <= c; i++) {
		char op;
		int x, y;
		cin >> op >> x >> y;
		if (op == 'Q') ++m, q[m] = query(x, y, t, m);
		else ++t, f[t][0] = modify(x, y), f[t][1] = modify(x, b[x]), b[x] = y;
	}
	s = max(1., pow(n, 2.0 / 3));
	sort(q + 1, q + 1 + m, [=] (query x, query y) {
		if (x.l / s != y.l / s) return x.l / s < y.l / s;
		if (x.r / s != y.r / s) return x.r / s < y.r / s;
		return x.t < y.t;
	});
	for (int i = 1; i <= m; i++) {
		while (r < q[i].r) add(++r);
		while (q[i].l < l) add(--l);
		while (q[i].r < r) rem(r--);
		while (l < q[i].l) rem(l++);
		while (k < q[i].t) mdf(++k, 0);
		while (q[i].t < k) mdf(k--, 1);
		ans[q[i].id] = cur;
	}
	for (int i = 1; i <= m; i++) cout << ans[i] << endl;
	return 0;
}