#include<bits/stdc++.h>
using namespace std;
struct wen{
	int l,r,i,t,ans;
}w[133340];
struct gai{
	int i,x,k;
}g[133340];
int n,m,k,a[133340],wi,gi,l,r,to[133340],tt,t;
char ch;
int read()
{
	int x = 0;
	char ch;
	ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - 48,ch = getchar();
	return x;
}
bool cmp(wen x,wen y)
{
	if((x.l - 1) / k == (y.l - 1) / k)
	{
		if(x.r == y.r) return x.t < y.t;
		return x.r < y.r;
	}
	return (x.l - 1) / k < (y.l - 1) / k;
}
bool cmp2(wen x,wen y)
{
	return x.i < y.i;
}
int main()
{
	n = read();
	m = read();
	for(int i = 1;i <= n;i++)
	{
		a[i] = read();
	}
	for(int i = 1;i <= m;i++)
	{
		cin >> ch;
		l = read(),r = read();
		if(ch == 'R')
		{
			g[++gi] = {l,a[l],r};
			t++;
		}
		else
		{
			w[++wi] = {l,r,i,t,0};
		}
	}
	k = sqrt(wi) + 0.5;
	sort(w + 1,w + 1 + wi,cmp);
	l = 1,r = 1,to[a[1]] = 1,tt = 1,t = 0;
	for(int i = 1;i <= wi;i++)
	{
		while(l < w[i].l)
		{
			to[a[l]]--;
			if(!to[a[l]]) tt--;
			l++;
		}
		while(l > w[i].l)
		{
			l--;
			to[a[l]]++;
			if(to[a[l]] == 1) tt++;
		}
		while(r < w[i].r)
		{
			r++;
			to[a[r]]++;
			if(to[a[r]] == 1) tt++;
		}
		while(r > w[i].r)
		{
			to[a[r]]--;
			if(!to[a[r]]) tt--;
			r--;
		}
		while(t < w[i].t)
		{
			t++;
			to[a[g[t].i]]--;
			if(!to[a[g[t].i]]) tt--;
			a[g[t].i] = g[t].k;
			to[a[g[t].i]]++;
			if(to[a[g[t].i]] == 1) tt++;
		}
		while(t > w[i].t)
		{
			to[a[g[t].i]]--;
			if(!to[a[g[t].i]]) tt--;
			a[g[t].i] = g[t].x;
			to[a[g[t].i]]++;
			if(to[a[g[t].i]] == 1) tt++;
			t--;
		}
		w[i].ans = tt;
	}
	sort(w + 1,w + 1 + wi,cmp2);
	for(int i = 1;i <= wi;i++)
	{
		printf("%lld\n",w[i].ans);
	}
	return 0;
}