#include<bits/stdc++.h>
using namespace std;
inline int readint(){
	int ans=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-f;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		ans=(ans<<3)+(ans<<1)+c-48;
		c=getchar();
	}
	return ans*f;
}
inline char readchar(){
	bk:
		char c=getchar();
		if(c>32&&c<127) return c;
		if(c==EOF) return 0;
	goto bk;
}
void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x<10) putchar(x+48);
	else{
		write(x/10);
		putchar(x%10+48);
	}
}
typedef pair<int,int>P;
int n,q;
struct edge{
	int x,y,t;
	int id;
	int ans;
};
edge s[140005];
int cnt1;
edge h[140005];
int cnt2;
int T;
inline bool cmp(edge a,edge b){
	if((a.x-1)/T!=(b.x-1)/T) return a.x<b.x;
	if((a.y-1)/T!=(b.y-1)/T) return a.y<b.y;
	return a.t<b.t;
}
vector<P>g[140005];
int now[1000005],nowans,l,r,t;
inline int getnum(int u,int t){
	P w=P(t,0x3f3f3f3f);
//	cout<<u<<' '<<t<<' '<<lower_bound(g[u].begin(),g[u].end(),w)-g[u].begin()-1<<' '<<g[u].size()<<endl;
	return g[u][lower_bound(g[u].begin(),g[u].end(),w)-g[u].begin()-1].second;
}
int out[140005];
int main(){
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);
	n=readint(); q=readint();
	T=pow(n,0.6667); 
	for(register int i=1;i<=n;i++){
		g[i].push_back(P(0,readint()));
	}
	for(register int i=1;i<=q;i++){
		edge e;
		char ch=readchar();
		e.x=readint(); e.y=readint();
		e.t=i;
		if(ch=='Q'){
			e.id=++cnt1;
			s[e.id]=e;
		}else{
			g[e.x].push_back(P(e.t,e.y));
			h[i]=e;
		}
	}
	for(register int i=1;i<=n;i++) g[i].push_back(P(0x3f3f3f3f,0x3f3f3f3f));
	sort(s+1,s+1+cnt1,cmp);
	l=1,r=0,t=0;
	for(register int i=1;i<=cnt1;i++){
		while(l>s[i].x){
			int yy=getnum(--l,t);
			if(!now[yy]) nowans++;
			now[yy]++;
//			cout<<l<<' '<<r<<' '<<t<<' '<<nowans<<'\n';
		}
		while(r<s[i].y){
			int yy=getnum(++r,t);
			if(!now[yy]) nowans++;
			now[yy]++;
//			cout<<l<<' '<<r<<' '<<t<<' '<<nowans<<'\n';
		}
		while(l<s[i].x){
			int yy=getnum(l++,t);
			now[yy]--;
			if(!now[yy]) nowans--;
//			cout<<l<<' '<<r<<' '<<t<<' '<<nowans<<'\n';
		}
		while(r>s[i].y){
			int yy=getnum(r--,t);
			now[yy]--;
			if(!now[yy]) nowans--;
//			cout<<l<<' '<<r<<' '<<t<<' '<<nowans<<'\n';
		}
		while(t>s[i].t){
			if(l<=h[t].x&&h[t].x<=r){
				int xx=getnum(h[t].x,t-1),yy=getnum(h[t].x,t);
				if(!now[xx]) nowans++;
				now[xx]++;
				now[yy]--;
				if(!now[yy]) nowans--;
			}
			t--;
//			cout<<l<<' '<<r<<' '<<t<<' '<<nowans<<'\n';
		}
		while(t<s[i].t){
			if(l<=h[t+1].x&&h[t+1].x<=r){
//				cout<<getnum(h[t].x,t+1);
				int xx=getnum(h[t+1].x,t+1);
				int yy=getnum(h[t+1].x,t);
				if(!now[xx]) nowans++;
				now[xx]++;
//				cout<<h[t+1].x<<' '<<t+1<<' '<<getnum(h[t+1].x,t+1)<<'\n';
//				cout<<h[t+1].x<<' '<<t<<' '<<getnum(h[t+1].x,t)<<endl;
				now[yy]--;
				if(!now[yy]) nowans--;
			}
			t++;
//			cout<<l<<' '<<r<<' '<<t<<' '<<nowans<<'\n';
		}
		s[i].ans=nowans;
		out[s[i].id]=nowans;
	}
	for(register int i=1;i<=cnt1;i++){
		write(out[i]);
		putchar(10);
	}
	return 0;
}