#include <bits/stdc++.h>
using namespace std;

int a[200005];
int m[200005];
int u[200005];
struct node{
	int l,r,k,t,ans,bh;
}b[200005];
struct node1{
	int v,x,x2;
}c[200005];
bool cmp(node x,node y){
	if (x.k==y.k){
		return x.r<y.r;
	}
	return x.k<y.k;
}
bool cmp1(node x,node y){
	return x.bh<y.bh; 
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int n,m1;
	cin>>n>>m1; 
	for(int i=1;i<=n;i++){
		cin>>a[i];
		u[i]=a[i];
	}
	int k=0;
	int p1=0,p2=0;
	for(int i=1;i<=m1;i++){
		char c1;
		cin>>c1;
		if (c1=='Q') {
			p1++;
			b[p1].bh=p1;
			cin>>b[p1].l>>b[p1].r;
			b[p1].t=p2;
		}
		else{
			p2++;
			cin>>c[p2].v>>c[p2].x;
			c[p2].x2=u[c[p2].v];
			u[c[p2].v]=c[p2].x;
		}
	}
	int v=1+sqrt(p1);
	for(int i=1;i<=p1;i++){
		b[i].k=(b[i].l-1)/v+1;
		k=max(k,b[i].k);
	}
	sort(b+1,b+1+p1,cmp);
	int w=1;
	for(int i=1;i<=k;i++){
		memset(m,0,sizeof(m));
		int u=w;
		while(b[u].k==b[u+1].k) u++;
		int l=b[w].l,r=b[w].r;
		int ans=0;
		for(int j=l;j<=r;j++){
			m[a[j]]++;
			if (m[a[j]]==1) ans++;
		}
		for(int j=1;j<=b[w].t;j++){
			int r=c[j].v;
			m[c[j].x2]--;
			if(m[c[j].x2]==0) ans--;
			m[c[j].x]++;
			if (m[c[j].x]==1) ans++;
		}
		int t=b[w].t;
		for(int j=w;j<=u;j++){
			while(b[j].l<l){
				l--;
				m[a[l]]++;
				if (m[a[l]]==1) ans++;
			}
			while(b[j].l>l){
				m[a[l]]--;
				if (m[a[l]]==0) ans--;
				l++; 
			}
			while(r<b[j].r){
				r++;
				m[a[r]]++;
				if (m[a[r]]==1) ans++;
			}
			while(t<b[j].t){
				t++;
				m[c[t].x2]--;
				if(m[c[t].x2]==0) ans--;
				m[c[t].x]++;
				if (m[c[t].x]==1) ans++;
			}
			while(t>b[j].t){
				m[c[t].x]--;
				if (m[c[t].x]==0) ans--;
				m[c[t].x2]++;
				if (m[c[t].x2]==1) ans++;
			}
			b[j].ans=ans;
		}
	}
	sort(b+1,b+1+p1,cmp1);
	for(int i=1;i<=p1;i++) cout<<b[i].ans<<endl; 
	return 0;
}