#include<bits/stdc++.h>

#define inf 1000000000

#define ll long long

#define N 10005

#define M 1000005

using namespace std;

int read(){

  int x=,f=;char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

  while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

  return x*f;

}

int block,n,m,q;

int a[N],b[N],c[N],pre[M],pos[N];

char ch[];

void reset(int x){

  int l=(x-)*block+,r=min(x*block,n);

  for(int i=l;i<=r;i++)b[i]=a[i];

  sort(b+l,b+r+);

}

void update(int x,int v){

  for(int i=;i<=n;i++)pre[c[i]]=;

  c[x]=v;

  for(int i=;i<=n;i++){

    int t=a[i];

    a[i]=pre[c[i]];

    if(t!=a[i])reset(pos[i]);

    pre[c[i]]=i;

  }

}

int find(int x,int v){

  int l=(x-)*block+,r=x*block,mid,tmp;

  while(l<=r){

    mid=l+r>>;

    if(b[mid]<v)tmp=mid,l=mid+;

    else r=mid-;

  }

  return tmp-(x-)*block;

}

int query(int l,int r){

  int ans=;

  if(pos[l]==pos[r]){

    for(int i=l;i<=r;i++)if(a[i]<l)ans++;

  }

  else{

    for(int i=l;i<=block*pos[l];i++)if(a[i]<l)ans++;

    for(int i=(pos[r]-)*block+;i<=r;i++)if(a[i]<l)ans++;

  }

  for(int i=pos[l]+;i<pos[r];i++)ans+=find(i,l);

  return ans;

}

int main(){

  n=read();q=read();

  for(int i=;i<=n;i++){

    c[i]=read();a[i]=pre[c[i]];

    pre[c[i]]=i;

  }

  block=(int)sqrt(n);

  for(int i=;i<=n;i++)pos[i]=(i-)/block+;

  if(n%block)m=n/block+;else m=n/block;

  for(int i=;i<=m;i++)reset(i);

  while(q--){

    scanf("%s",ch);

    int x=read(),y=read();

    if(ch[]=='Q')printf("%d\n",query(x,y));

    else update(x,y);

  }

  return ;

}