#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
const int N=4e5+10;
int n,m,a[N];
int len,num;
int paw[N],paz[N];
struct qu{
	int l,r,t,ans;
}q[N];
struct ga{
	int w,c;
}g[N];
void init(){
	len=pow(n,0.666);
	num=(n+len-1)/len;
}
bool cmp(qu a,qu b){
	if(a.l/len==b.l/len){
		if(a.r==b.r) return a.t<b.t;
		return a.r<b.r;
	}
	return a.l/len<b.l/len;
}
bool cmp1(qu a,qu b){
	return a.t<b.t;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	init();
	int cnt=1;
	for(int i=1;i<=m;i++){
		char s;
		cin>>s;
		if(s=='Q') cin>>q[cnt].l>>q[cnt].r,q[cnt++].t=i;
		else cin>>g[i].w>>g[i].c;
	}
	sort(q+1,q+cnt,cmp);
	int l=1,r=0,tim=0,ans=0;
	int t[N];
	memset(t,0,sizeof t);
	for(int i=1;i<cnt;i++){
		while(l<q[i].l){
			t[a[l]]--;
			if(t[a[l]]==0) ans--;
			l++;
		}
		while(l>q[i].l){
			l--;
			if(!t[a[l]]) ans++;
			t[a[l]]++;
		}
		while(r<q[i].r){
			r++;
			if(!t[a[r]]) ans++;
			t[a[r]]++;
		}
		while(r>q[i].r){
			t[a[r]]--;
			if(!t[a[r]]) ans--;
			r--;
		}
		while(tim<q[i].t){
			tim++;
			if(g[tim].w){
				paw[tim]=g[tim].w;
				paz[tim]=a[g[tim].w];
				t[a[g[tim].w]]--;
				if(g[tim].w>=q[i].l and g[tim].w<=q[i].r){
					if(!t[a[g[tim].w]]) ans--;
				}
				a[g[tim].w]=g[tim].c;
				t[a[g[tim].w]]++;
				if(g[tim].w>=q[i].l and g[tim].w<=q[i].r){
					if(t[a[g[tim].w]]==1) ans++;
				}
			}
//			for(int j=1;j<=n;j++) cout<<a[j]<<" ";
//			cout<<"\n";
		}
		while(tim>q[i].t){
			tim--;
			if(paw[tim]){
				t[paz[tim]]--;
				if(paw[tim]>=q[i].l and paw[tim]<=q[i].r){
					if(!t[paz[tim]]) ans--;
				}
				a[paw[tim]]=paz[tim];
				t[paz[tim]]++;
				if(paw[tim]>=q[i].l and paw[tim]<=q[i].r){
					if(t[paz[tim]]==1) ans++;
				}  
			}
//			for(int j=1;j<=n;j++) cout<<a[j]<<" ";
//			cout<<"\n";
		}
		q[i].ans=ans;
	}
	sort(q+1,q+cnt,cmp1);
	for(int i=1;i<cnt;i++){
		cout<<q[i].ans<<endl;
	}
//	for(int i=1;i<=n;i++){
//		cout<<paw[i]<<" "<<paz[i]<<"\n";
//	}
	return 0;
}