RT

#include<bits/stdc++.h>
#define time abcdefg
using namespace std;
int n,m,a[2000005],x,y,l=1,r,num1,num2,block,num[2000005],cnt[2000005],sum,t,ans[2000005];
char opt;
struct node1 {
	int l,r,p,time;
} q[2000005];
struct node2 {
	int p,pre,nxt;
} c[2000005];
bool cmp(node1 a,node1 b) {
	if(num[a.l]!=num[b.l])return a.l<b.l;
	if(num[a.r]!=num[b.r])return a.r<b.r;
	return a.time<b.time;
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)scanf("%d",&a[i]);
	for(int i=1; i<=m; i++) {
		cin>>opt>>x>>y;
		if(opt=='R')
			c[++num1].p=x,c[num1].nxt=y,c[num1].pre=a[x],a[x]=y;
		else q[++num2].l=x,q[num2].r=y,q[num2].p=num2,q[num2].time=num1;
	}
	block=pow(n,4.0/3.0)*pow(num1,1.0/3.0);
	for(int i=1; i<=n; i++)num[i]=(i/block)+(i%block!=0);
	for(int i=num1; i>=1; i--)a[c[i].p]=c[i].pre;
	sort(q+1,q+num2+1,cmp);
	for(int i=1; i<=num2; i++) {
		while(l<q[i].l) {
			cnt[a[l]]--;
			if(!cnt[a[l]])sum--;
			l++;
		}
		while(l>q[i].l) {
			l--;
			if(!cnt[a[l]])sum++;
			cnt[a[l]]++;
		}
		while(r<q[i].r) {
			r++;
			if(!cnt[a[r]])sum++;
			cnt[a[r]]++;
		}
		while(r>q[i].r) {
			cnt[a[r]]--;
			if(!cnt[a[r]])sum--;
			r--;
		}
		while(t<q[i].time) {
			t++;
			int p=c[t].p;
			if(p>=l&&p<=r)cnt[a[p]]--;
			if(!cnt[a[p]])sum--;
			a[p]=c[t].nxt;
			if(p>=l&&p<=r)cnt[a[p]]++;
			if(cnt[a[p]]==1)sum++;
		}
		while(t>q[i].time){
			int p=c[t].p;
			if(p>=l&&p<=r)cnt[a[p]]--;
			if(!cnt[a[p]])sum--;
			a[p]=c[t--].pre;
			if(p>=l&&p<=r)cnt[a[p]]++;
			if(cnt[a[p]]==1)sum++;
		}
		ans[q[i].p]=sum;
	}
	for(int i=1;i<=num2;i++)printf("%d\n",ans[i]);
}