rt

//# pragma GCC optimize("Ofast,no-stack-protector")
//
//# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

# include <bits/stdc++.h>

# define I return

# define AK 0

# define IOI ;

using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

int n, m, Q, len, pie[133340], a[133340], l, r, ans[133340], sum, s[1000005], T, id[133340], col[133340], t;

char op;

struct node {

	int l, r, t, id;

	bool operator < (const node& a) const {

		return pie[l] != pie[a.l] ? pie[l] < pie[a.l] : pie[r] != pie[a.r] ? pie[r] & 1 ? pie[r] > pie[a.r] : pie[r] < pie[a.r] : t < a.t;

	}

} q[133340];

void add (const int x) {

	if (! s[x])
		++ sum;

	++ s[x];
//	cerr << "add " << l << '~' << r << ',' << t << ':' << sum << '\n';
	return ;

}

void del (const int x) {

	if (! -- s[x])
		-- sum;
//	cerr << "del " << l << '~' << r << ',' << t << ':' << sum << '\n';
	return ;

}

void timechange (const int x) {

	if (id[x] >= l && id[x] <= r)
		del (a[id[x]]), add (col[x]);

	swap (a[id[x]], col[x]);
//	cerr << "time " << l << '~' << r << ',' << t << ':' << sum << '\n';
	return ;

}

int main () {

	ios::sync_with_stdio (0);

	cin.tie (0);

	cout.tie (0);

	cin >> n >> Q;

	for (int i = 1; i <= n; ++ i)
		cin >> a[i];

	len = pow (n, 2 / 3.0);

	for (int i = 1; i <= n; ++ i)
		pie[i] = i / len;

	while (Q --) {

		cin >> op >> l >> r;

		if (op == 'Q')
			q[m] = {l, r, T, m}, ++ m;
		else
			id[++ T] = l, col[T] = r;

	}

	sort (q, q + m);

	l = 1, r = 0;

	for (int i = 0; i < m; ++ i) {

		while (l > q[i].l)
			add (a[-- l]);

		while (r < q[i].r)
			add (a[++ r]);

		while (l < q[i].l)
			del (a[l]), ++ l;

		while (r > q[i].r)
			del (a[r]), -- r;

		while (t < q[i].t)
			timechange (++ t);

		while (t > q[i].t)
			timechange (t), -- t;

		ans[q[i].id] = sum;

	}

	for (int i = 0; i < m; ++ i)
		cout << ans[i] << '\n';

	I AK IOI

}
/*
6 2
1 2 3 4 5 5
R 1 2
Q 1 6
*/