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]);
}