#include<bits/stdc++.h>
#define add(x)mp[x]++,tot+=(mp[x]==1),tot-=(mp[x]==2)
#define del(x)tot+=(mp[x]==2),tot-=(mp[x]==1),mp[x]--
#pragma optimize(2)
#pragma optimize(3)
#pragma optimize("Ofast")
#pragma optimize("inline")
char *p1,*p2,buf[1<<21];
//#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
#define readin(fn) FILE *fin = freopen(#fn ".in", "r", stdin)
#define output(fn) FILE *fout = freopen(#fn ".out", "w", stdout)
using namespace std;
const int N=2e5+25;
struct Query{
    int l,r,toki,id;
}q[N];
struct Modify{
    int pos,c;
}r[N];
int pos[N],n,a[N],m;
int mp[N],qcnt,rcnt;
inline int read(){
    int x=0;
    char ch=getchar();
    while(ch<48|ch>57)
        ch=getchar();
    while(ch>=48&&ch<=57)
        x=(x*10)+(ch^48),ch=getchar();
    return x;
}
inline void write(int x) {
    static int sta[40];
    int top=0;
    do{sta[top++]=x%10,x/=10;}while(x);
    while(top)putchar(sta[--top]+48);
}
inline bool cmp(Query x,Query y){
    if(pos[x.l]!=pos[y.l])return x.l<y.l;
    if(pos[x.r]!=pos[y.r])return x.r<y.r;
    if(pos[x.l]%2==0)return x.toki<y.toki;
    return x.toki>y.toki;
}
int tot;
int ans[N];
signed main(){
    //readin(data);
    //output(bf);
    cin>>n>>m;
    int len=pow(n,2.0/3.0);
    for(int i=1;i<=n;i++)
        cin>>a[i],pos[i]=i/len;
    int opt;
    for(int i=1;i<=m;i++){
        cin>>opt;
        if(opt==2){
            ++qcnt;
            q[qcnt].l=read(),q[qcnt].r=read();
            q[qcnt].l++,q[qcnt].r++;
            q[qcnt].toki=rcnt,q[qcnt].id=qcnt;
        }else{
            ++rcnt;
            r[rcnt].pos=read(),r[rcnt].c=read();
            r[rcnt].pos++;
        }
    }
    sort(q+1,q+1+qcnt,cmp);
    int lp=1,rp=0,lst=0;
    for(int i=1;i<=qcnt;i++){
        while(lp>q[i].l)--lp,add(a[lp]);
        while(rp<q[i].r)++rp,add(a[rp]);
        while(lp<q[i].l)del(a[lp]),++lp;
        while(rp>q[i].r)del(a[rp]),--rp;
        while(q[i].toki>lst){
            ++lst;
            if(r[lst].pos>=lp&&r[lst].pos<=rp){
                del(a[r[lst].pos]);
                add(r[lst].c);
            }
            swap(a[r[lst].pos],r[lst].c);
        }
        while(q[i].toki<lst){
            if(r[lst].pos>=lp&&r[lst].pos<=rp){
                del(a[r[lst].pos]);
                add(r[lst].c);
            }
            swap(a[r[lst].pos],r[lst].c);
            --lst;
        }
        ans[q[i].id]=tot;
    }
    for(int i=1;i<=qcnt;i++)
        write(ans[i]),puts("");
}