#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

int n, m, block;
int cntc, cntq;
int a[N], bel[N];

struct Query {
	int l, r, times, id;
	Query () {}
	Query (int _l, int _r, int _times, int _id) { l = _l, r = _r, times = _times, id = _id; }
	friend bool operator < (const Query& q1, const Query& q2) {
		if (bel[q1.l] == bel[q2.l]) {
			if (bel[q1.r] == bel[q2.r]) return q1.times < q2.times;
			return q1.r < q2.r;
		}
		return q1.l < q2.l;
	}
} q[N] ;

struct Modify {
	int pos, col;
	Modify () {}
	Modify (int _pos, int _col) { pos = _pos, col = _col; }
} c[N] ;

int cnt[N];
int l = 1, r, t, ans, rs[N];

void add (int x) {
	if (++cnt[x] == 1) ++ans;
}

void del (int x) {
	if (--cnt[x] == 0) --ans;
}

void move (int x, int ind) {
	int ql = q[ind].l, qr = q[ind].r;
	if (c[x].pos >= ql && c[x].pos <= qr) del(a[c[x].pos]), add(c[x].col);
	swap(c[x].col, a[c[x].pos]);
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("P1903.in", "r", stdin);
	freopen("P1903.out", "w", stdout);
#endif
	cin >> n >> m; block = pow(n, 2.0 / 3);
	for (int i = 1; i <= n; ++i) { 
		cin >> a[i];
		if (i % block == 0) bel[i] = i / block;
		else bel[i] = i / block + 1;
	}
	for (int i = 1; i <= m; ++i) {
		char opt; int l, r;
		cin >> opt >> l >> r;
		if (opt == 'Q') q[++cntq] = Query(l, r, cntc, cntq);
		else c[++cntc] = Modify(l, r);
	}
	sort(q + 1, q + 1 + cntq);
	for (int i = 1; i <= cntq; ++i) {
		int ql = q[i].l, qr = q[i].r, qt = q[i].times;
		while (l < ql) del(a[l++]);
		while (l > ql) add(a[--l]);
		while (r < qr) add(a[++r]);
		while (r > qr) del(a[r--]);
		while (t < qt) move(++t, i);
		while (t > qt) move(t--, i);
		rs[q[i].id] = ans;
	}
	for (int i = 1; i <= cntq; ++i) cout << rs[i] << endl;
	return 0;
}