#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N = 1e6+5;
int n, m,M;
int a[N];
int cnt[N],tot,ans[N];
int cnt_c,cnt_q;
struct node {
	int l,r,t,id;
	inline friend bool operator < (node fi,node se) {
		return fi.l/M==se.l/M ?
		       ( fi.r/M==se.r/M ? fi.t<se.t : fi.r<se.r )
			       : fi.l<se.l;
	}
};
node qu[N],ch[N];
inline void add(int x) {
	if(!cnt[a[x]]) ++tot;
	++cnt[a[x]];
}
inline void del(int x) {
	--cnt[a[x]];
	if(!cnt[a[x]]) --tot;
}
signed main() {
	cin>>n>>m;
	M=pow(n,0.666);
	for(int i=1; i<=n; ++i) scanf("%d",&a[i]);
	for(int i=1; i<=m; ++i) {
		string opt;
		cin>>opt;
		int l,r;
		scanf("%d%d",&l,&r);
		if(opt[0]=='Q') {
			++cnt_q;
			qu[cnt_q]=<%l,r,cnt_c,cnt_q%>;

		} else {
			++cnt_c;
			ch[cnt_c]=<%l,r,cnt_q,cnt_c%>;

		}
	}
	int l=1,r=0,t=0;
	sort(qu+1,qu+cnt_q+1);
	for(int i=1; i<=cnt_q; ++i) {
		while(qu[i].l<l) add(--l);
		while(qu[i].r>r) add(++r);
		while(qu[i].l>l) del(l++);
		while(qu[i].r<r) del(r--);
		while(t<qu[i].t) {
			++t;
			if(l<=ch[t].l&&ch[t].l<=r) {
				del(a[ch[t].l]);
				add(ch[t].r);
			}
			swap(a[ch[t].l],ch[t].r);
		}
		while(qu[i].t<t) {
			if(l<=ch[t].l&&ch[t].l<=r) {
				del(a[ch[t].l]);
				add(ch[t].r);
			}
			swap(a[ch[t].l],ch[t].r);
			--t;
		}
		ans[qu[i].id]=tot;
	}
	for(int i=1; i<=cnt_q; ++i) printf("%d\n",ans[i]);
	return 0;
}