rt

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 20;
ll n, m, a[N];
ll siz = 0, cnt[N], cq = 0, cc = 0;
ll ans[N], num = 0;
struct query{
	ll l, r, t, id;
}q[N];
struct change{
	ll pos, x;
}c[N];

bool cmp(query a, query b) {
	return a.l / siz == b.l / siz ? a.r / siz == b.r / siz ? a.t < b.t : a.r < b.r : a.l < b.l;
//return a.l / sz == b.l / sz ? a.r / sz == b.r / sz ? a.t < b.t : a.r < b.r : a.l < b.l;
}


int main (){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	siz = pow(n, 2.0 / 3.0);
	for(int i = 1; i <= m; i++) {
		string op;
		ll l, r;
		cin >> op;
		scanf("%d%d", &l, &r);
		if(op == "Q") {
			q[++cq] = (query){l, r, cc, cq};
		}
		else if(op == "R") {
			c[++cc] = (change){l, r};
		}
	}
	sort(q + 1, q + cq + 1, cmp);
	ll l = 1, r = 0, time = 0;
	num = 0;
	for(int i = 1; i <= cq; i++) {
		ll ql = q[i].l, qr = q[i].r, qt = q[i].t;
		while(ql < l) num += !cnt[a[--l]]++;
		while(r < qr) num += !cnt[a[++r]]++;
		while(l < ql) num -= !--cnt[a[l++]];
		while(r > qr) num -= !--cnt[a[r--]];
//		cout << ql << " " << qr << " " << t << " " << num << endl;
		if(time < qt) {
			time++;
			if(ql <=  c[time].pos && c[time].pos <= qr) num = num - (!--cnt[a[c[time].pos]]) + (!cnt[c[time].x]++);
			swap(a[c[time].pos], c[time].x);
		}
		
		if(time > qt) {
			if(ql <=  c[time].pos && c[time].pos <= qr) num = num - (!--cnt[a[c[time].pos]]) + (!cnt[c[time].x]++);
			swap(a[c[time].pos], c[time].x);
			time--;
		}
//		cout << ql << " " << qr << " " << qt << " " << num << endl;
		ans[q[i].id] = num;
	}
	for(int i = 1; i <= cq; i++) printf("%d\n", ans[i]);
	return 0;
}