/*input
7 5
1 3 2 1 4 2 3
1 1 4
2 2 3
1 1 7
2 4 5
1 1 7


*/

#include <bits/stdc++.h>
#include <unistd.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

#define rep(i,j,n) for(i=j;i<n;i++)
#define repi(i,j,n) for(i=j;i>n;i--)
#define inf 1e18
#define M 1000000007
#define pie 3.141592653589793238
#define ll int
#define ld long double
#define vll vector<int>
#define vi vector<int>
#define pll pair<int,int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define vpll vector<pair<int,int> >
#define pb push_back
#define pf pop_front
#define F first
#define S second
#define endl '\n'
#define N 1001000

using namespace std;
using namespace __gnu_pbds; 

template<typename T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


ll power(ll a,ll m,ll mod){
	ll ans=1;
	while(m){
		if(m%2){
			ans*=a;
			ans%=(mod);
		}
		a=(a*a)%(mod);
		m>>=1;
	}
	return ans;
}


void init(ll* a,ll n,ll val){
	for(ll i=0;i<n;i++)
		a[i]=val;
}

int a[N],sb[4*N],se[4*N],pre[N],b[N];
unordered_set<ll> sz[N];
vll st[4*N];
set<ll> v[N];
vll bit[4*N];
ll q[3][N];

void build(int node,int l,int r){
	sb[node]=l;
	se[node]=r;
	ll i,z;
	rep(i,l,r+1){
		for(auto j : sz[i])st[node].pb(j);
	}
	sort(st[node].begin(),st[node].end());
	st[node].erase(unique(st[node].begin(),st[node].end()),st[node].end());
	bit[node].resize(st[node].size()+1,0);
	rep(i,l,r+1){
		z=pre[i];
		z=lower_bound(st[node].begin(),st[node].end(),z)-st[node].begin()+1;
		while(z<bit[node].size()){
			bit[node][z]+=b[i];
			z+=z&-z;
		}
	}
	if(l==r){
		return;	
	}
	int mid=(l+r)/2;
	build(2*node,l,mid);
	build(2*node+1,mid+1,r);
	return;
}

int query(int node,int l,int r){
	if(sb[node]>r||se[node]<l)	
		return 0;
	if(sb[node]>=l&&se[node]<=r){
		ll ans=0;
		ll z=bit[node].size()-1;
		while(z>0){
			ans+=bit[node][z];
			z-=z&-z;
		}
		z=lower_bound(st[node].begin(),st[node].end(),l)-st[node].begin();
		while(z>0)ans-=bit[node][z],z-=z&-z;
		return ans;
	}
	int left=query(2*node,l,r);
	int right=query(2*node+1,l,r);
	return left+right;
}

void update(int node,int p,int val){
	if(sb[node]>p||se[node]<p)	
		return;
	ll z=pre[p];
	z=lower_bound(st[node].begin(),st[node].end(),z)-st[node].begin()+1;
	while(z<bit[node].size()){
		bit[node][z]+=val*b[p];
		z+=z&-z;
	}

	update(2*node,p,val);
	update(2*node+1,p,val);
}

set<ll> :: iterator it,it1,it2;
void solve(int which, int kk){
	ll i,j,k;
	k=q[0][kk];
	--k;
	if(k){
		ll l,r;
		l=q[1][kk],r=q[2][kk];
		if(which)cout<<query(1,l,r)<<endl;
		return;
	}
	ll p,x;
	p=q[1][kk],x=q[2][kk];
	j=a[p];
	a[p]=x;
    it=v[j].find(p);
	if(which)update(1,p,-1);
	it1=it;
	++it1;
	v[j].erase(it);
	if(it1!=v[j].end()){
		if(which)update(1,*it1,-1);
		if(it1==v[j].begin())pre[*it1]=*it1;
		else {
			it=it1;
			--it;
			pre[*it1]=*it;
		}
		b[*it1]=*it1-pre[*it1];
		if(which)update(1,*it1,1);
		else sz[*it1].insert(pre[*it1]);
	}
	v[x].insert(p);
	it=v[x].find(p);
	it1=it;
	it2=it;
	--it2;
	++it1;
	if(it1!=v[x].end()){
		if(which)update(1,*it1,-1);
		pre[*it1]=*it;
		b[*it1]=*it1-pre[*it1];
		if(which)update(1,*it1,1);
		else sz[*it1].insert(pre[*it1]);
	}
	if(it==v[x].begin()){
		pre[*it]=*it;
	}else pre[*it]=*it2;
	b[*it]=*it-pre[*it];
	if(which)update(1,*it,1);
	else sz[*it].insert(pre[*it]);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);	
	ll T=1,n,i,j;
	cin>>n>>T;
	ll a1[n+1];
	rep(i,1,n+1)cin>>a[i],a1[i]=a[i];
	rep(i,0,T)rep(j,0,3)cin>>q[j][i];
	map<ll,ll> mp;
	rep(i,1,n+1){
		if(mp.find(a[i])==mp.end())pre[i]=i;
		else pre[i]=mp[a[i]];
		mp[a[i]]=i;
		b[i]=i-pre[i];
		v[a[i]].insert(i);
 		sz[i].insert(pre[i]);
	}
	rep(i,0,T)solve(0,i);
	mp.clear();
	rep(i,1,n+1)a[i]=a1[i],v[i].clear();
	rep(i,1,n+1){
		if(mp.find(a[i])==mp.end())pre[i]=i;
		else pre[i]=mp[a[i]];
		mp[a[i]]=i;
		b[i]=i-pre[i];
		v[a[i]].insert(i);
	}
	build(1,1,n);
	rep(i,0,T)solve(1,i);
	return 0;
}


