#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
 
const int N=2e5+7;
ll mod=1e9+7;
ll ax[8]={0,0,-1,+1,-1,-1,1,1};
ll ay[8]={-1,1,0,0,-1,1,-1,1};
ll kx[8]={2,2,-2,-2,1,1,-1,-1};
ll ky[8]={1,-1,1,-1,2,-2,2,-2};

struct query{
	ll id,l,r,t;
}Q[N];
struct update{
	ll pos,old,cur;
}U[N];
ll ans[N],a[N],last[N],cnt[N],l,r,t,dis;
void add(ll val){
	cnt[val]++;
	if(cnt[val]==1) dis++;
	if(cnt[val]==2) dis--;
}
void del(ll val){
	cnt[val]--;
	if(cnt[val]==1) dis++;
	if(cnt[val]==0) dis--;
}
void update(ll val,ll pos,ll t){
	U[t].old=a[pos];
	if(pos>l && pos<=r) {add(val);del(a[pos]);}
	a[pos]=val;		
}
int main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
    ll tt=1;
    //cin>>tt; 
    while(tt--){
    	ll i,j,n,q,s=0;
    	cin>>n>>q;
    	dis=0;
    	ll sz= pow(n, 2./3.)+1;
    	for(i=0;i<n;i++){
    		cin>>a[i];last[i]=a[i];
    	}
    	ll up=0,qlen=0;
    	for(i=0;i<q;i++){
    		ll x,y,z;
    		cin>>x>>y>>z;
    		if(x==1){
    			U[++up]={y,last[y],z};
    			last[y]=z;    			
    		}
    		else{
    			Q[++qlen]={qlen,y,z,up};    			
    		}
    	}
    	sort(Q+1,Q+qlen+1,[&](query a,query b){
    		if((a.l)/sz==(b.l)/sz){
            if((a.r)/sz==(b.r)/sz) return a.t<b.t;
            return ((a.r)/sz)<((b.r)/sz);
         }
         return (a.l)<(b.l);
    	});
    	l=-1,r=-1,t=0;
    	for(i=1;i<=qlen;i++){
    		ll ql=Q[i].l-1,qr=Q[i].r,qt=Q[i].t;
    		while(t<qt) {t++;update(U[t].cur,U[t].pos,t);}
    		while(t>qt) {update(U[t].old,U[t].pos,t);t--;} 
    		while(l<ql) del(a[++l]); 
    		while(l>ql) add(a[l--]);
    		while(r>qr) del(a[r--]);
    		while(r<qr) add(a[++r]);
    		//cout<<Q[i].id<<" "<<i<<" "<<ql<<" "<<qr<<" "<<qt<<" "<<dis<<endl;
    		ans[Q[i].id]=dis; 		
    	}
    	for(i=1;i<=qlen;i++) cout<<ans[i]<<"\n";
	}
	return 0;
}