#include<iostream>
#include<stdio.h>
#include<cmath>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<queue>
#include<vector>
#include<map>
#define oo 0x3f3f3f3f
#define OO 0x3f3f3f3f3f3f3f3f
#define res register int 
#define LL long long
#define STP system("pause")
using namespace std;
const int N=2e6;
struct NODE{
	int l,r,tim,id;
}ask[N+5];
int a[N+5],pos[N+5],bec[N+5],re[N+5],Ans[N+5];
int col[N+5];
int Wid;//分块大小
int cmp(NODE x,NODE y){//排序
	if(x.l/Wid!=y.l/Wid)	return x.l<y.l;
	else if(x.r/Wid!=y.r/Wid)	return x.r<y.r;
	else return x.tim<y.tim;
}
int ans=0;
void Add(int x){
	if(!col[x])	++ans;
	++col[x];
	return ;
}
void Del(int x){
	--col[x];
	if(!col[x])	--ans;
	return ;
}
int main(){
//	freopen("c.in","r",stdin);
//	freopen("c.out","w",stdout);
	int n,m,t=0,k=0;
	cin>>n>>m;
	Wid=pow(n,0.666667);
	for(int i=1;i<=n;++i)	cin>>a[i];
	for(int i=1;i<=m;++i){
		char op;
		cin>>op;
		int l,r;
		cin>>l>>r;
		if(op=='Q'){
			if(l>r)	swap(l,r);
			ask[++t].id=t,ask[t].l=l,ask[t].r=r,ask[t].tim=k;
		}
		else{
			pos[++k]=l,bec[k]=r;
		}
	}
	sort(ask+1,ask+t+1,cmp);
	int L=1,R=1,T=0;
	ans=1;
	col[a[1]]=1;
	for(int i=1;i<=t;++i){
		while(L-1>=ask[i].l){
			Add(a[--L]);
		}
		while(R+1<=ask[i].r){
			Add(a[++R]);
		}
		while(L+1<=ask[i].l){
			Del(a[L++]);
		}
		while(R-1>=ask[i].r){
			Del(a[R--]);
		}
		while(T+1<=ask[i].tim){
			++T;
			if(pos[T]>=L&&pos[T]<=R){
				Add(bec[T]);Del(a[pos[T]]);
			}
			re[T]=a[pos[T]],a[pos[T]]=bec[T];//re是这个地方原本是什么数，bec是这个地方要变成什么数
		}	
		while(T-1>=ask[i].tim){
			if(pos[T]>=L&&pos[T]<=R){
				Del(a[pos[T]]);Add(re[T]);
			}
			a[pos[T]]=re[T];//再变回来
			--T;
		}
		Ans[ask[i].id]=ans;//统计答案
	}
	for(int i=1;i<=t;++i)	cout<<Ans[i]<<'\n';
	return 0;
}