#include <iostream>
#include <algorithm>
#include <utility>
#include <cmath>
#define p first
#define col second
#define int long long
using namespace std;
inline int read()
{
	int ans = 0, f = 0;
	char c = getchar();
	while (!isdigit(c))
		f |= (c == '-'), c = getchar();
	while (isdigit(c))
		ans = (ans << 3) + (ans << 1) + c - 48, c = getchar();
	return f ? -ans : ans;
}
void write(int x)
{
	if (x < 0)
		putchar('-'), x = -x;
	if (x > 9)
		write(x / 10);
	putchar(48 + x % 10);
}
constexpr int N = 133333 + 5;
constexpr int V = 1e6 + 5;
int n, Q, k, a[N];
int ans, sq, res[N];
struct question
{
	int l, r, ti, id;
	bool operator<(const question &x) const
	{
		if (l / sq != x.l / sq)
			return l / sq < x.l / sq;
		if (r / sq != x.r / sq)
			return r / sq < x.r / sq;
		return ti < x.ti;
	}
} q[N];
int tot, now, mp[V];
pair<int, int> t[N];
inline void add(int x)
{
	if (++mp[x] == 1)
		++ans;
}
inline void del(int x)
{
	if (--mp[x] == 0)
		--ans;
}
inline void up(int ti, int i)
{
	if (t[ti].p >= q[i].l && t[ti].p <= q[i].r)
	{
		add(t[ti].col);
		del(a[t[ti].p]);
	}
	swap(a[t[ti].p], t[ti].col);
}
inline void down(int ti, int i)
{
	if (t[ti].p >= q[i].l && t[ti].p <= q[i].r)
	{
		add(t[ti].col);
		del(a[t[ti].p]);
	}
	swap(a[t[ti].p], t[ti].col);
}
signed main()
{
	n = read();
	for (int i = 1; i <= n; ++i)
		a[i] = read();
	Q = read();
	for (int i = 1; i <= Q; ++i)
	{
		char opt;
		cin >> opt;
		if (opt == 'Q')
		{
			++tot;
			q[tot] = {read(), read(), now, tot};
		}
		else
			t[++now] = {read(), read()};
	}
	sq = pow(n, 1.0 / 3.0);
	sort(q + 1, q + tot + 1);
	int l = 1, r = 1, ti = 0;
	add(a[1]);
	for (int i = 1; i <= tot; ++i)
	{
		while (l < q[i].l)
			add(a[++l]);
		while (l > q[i].l)
			del(a[l--]);
		while (r < q[i].r)
			add(a[++r]);
		while (r > q[i].r)
			del(a[r--]);
		while (ti < q[i].ti)
			up(++ti, i);
		while (ti > q[i].ti)
			down(ti--, i);
		res[q[i].id] = ans;
	}
	for (int i = 1; i <= tot; ++i)
		write(res[i]), putchar('\n');
	return 0;
}