RT.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct as{
	int l,r,id,la;
}ans1[260005];
int n,kuai,m;
map<int,int> vis;
int a[260000],mcqh[260000];
struct czmg{
	int p,col;
}ans2[260005];
int l,r;
bool cmp(as a,as b){
	int l1=(a.l-1)/kuai+1,l2=(b.l-1)/kuai+1;
	int r1=(a.r-1)/kuai+1,r2=(b.r-1)/kuai+1;
	return l1^l2?l1<l2:(r1^r2?r1<r2:a.la<b.la);
} 
int cnt=0;
inline void add(int u){
	++vis[a[u]];
	if (vis[a[u]]==1) cnt++;
	if (vis[a[u]]==2) cnt--;
}
inline void del(int u){
	--vis[a[u]];
	if (vis[a[u]]==0) cnt--;
	if (vis[a[u]]==1) cnt++;
}
inline void change(int l,int r,int t){
	if (ans2[t].p>=l&&ans2[t].p<=r){
		--vis[a[ans2[t].p]];
		++vis[ans2[t].col];
		if (vis[a[ans2[t].p]]==0) cnt--;
		if (vis[a[ans2[t].p]]==1) cnt++;
		if (vis[ans2[t].col]==1) cnt++;
		if (vis[ans2[t].col]==2) cnt--;
	}
	swap(ans2[t].col,a[ans2[t].p]);
}
int main(){
    cin >> n >> m;
    kuai=(int)pow(1.0*n,2.0/3.0);
    for (register int i=1;i<=n;i++){
    	cin >> a[i];
    }
    int len1=0,len2=0;
    for (register int i=1;i<=m;i++){
    	int qwq;
    	cin >> qwq;
    	if (qwq==2){
    		int l,r;
    		cin >> l >> r;
    		l++,r++;
    		ans1[++len1].l=l,ans1[len1].r=r;
    		ans1[len1].id=len1,ans1[len1].la=len2; 
    	}
    	else {
    		int p,col;
    		cin >> p >> col;
    		p++;
    		ans2[++len2].p=p,ans2[len2].col=col;
    	}
    }
    sort(ans1+1,ans1+1+len1,cmp);
    l=1,r=0;
    int t=0;
    for (register int i=1;i<=len1;i++){
	    while(l>ans1[i].l) add(--l);
    	while(l<ans1[i].l) del(l++);
		while(r>ans1[i].r) del(r--);
    	while(r<ans1[i].r) add(++r);
    	while(t<ans1[i].la) change(l,r,++t);
    	while(t>ans1[i].la) change(l,r,t--);
    	mcqh[ans1[i].id]=cnt;
    }
    for (register int i=1;i<=len1;i++){
    	cout << mcqh[i] << endl;
    }
    return 0;
}