#include<bits/stdc++.h>

#define maxn 100000+5
#define maxt 10000000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

struct Treap{
  int s[2],val,par;
}tr[maxn];

struct Segtree{
  int s[2];ll v;
}Tr[maxt];

int bit[maxn];
int a[maxn],root[maxn],link[maxn];
int n,m,size;

void rotate(int &x,int t){
  int s=tr[x].s[t];
  tr[s].par=tr[x].par,tr[tr[s].s[t^1]].par=x,tr[x].par=s;
  tr[x].s[t]=tr[s].s[t^1],tr[s].s[t^1]=x,x=s;
}

void Insert(int &x,int k,int p){
  if( x==0 ){
    x=k,tr[x].val=rand(),tr[x].par=p;
    return ;
  }
  int t=x<k;
  Insert(tr[x].s[t],k,x);
  if( tr[k].val>tr[x].val ) rotate(x,t);
}

bool Delete(int &x,int k){
  if( x==0 ) return true;
  if( x==k ){
    int l=tr[x].s[0],r=tr[x].s[1];
    if( l+r ){
      int t=tr[l].val<tr[r].val;
      rotate(x,t);
      return Delete(tr[x].s[t^1],k);
    }
    else x=0;
    return false;
  }
  return Delete(tr[x].s[(x<k)],k);
}

int Find_pre(int x,int p){
  if( x==0 ) return 0;
  if( x<p ){
    int t=Find_pre(tr[x].s[1],p);
    return max(x,t);
  }
  else return Find_pre(tr[x].s[0],p);
}

int Find_sub(int x,int p){
  if( x==0 ) return n+1;
  if( p<x ){
    int t=Find_sub(tr[x].s[0],p);
    return min(x,t);
  }
  else return Find_sub(tr[x].s[1],p);
}

void Revamp(int &x,int l,int r,int p,int v){
  if( x==0 ) x=++size;
  Tr[x].v+=v;
  if( l==r ) return ;
  if( p<=(l+r)/2 ) Revamp(Tr[x].s[0],l,(l+r)/2,p,v);
  else Revamp(Tr[x].s[1],(l+r)/2+1,r,p,v);
}

void Modify(int x,int p,int w){
  for(int i=p;i>0;i-=i&-i)
    Revamp(bit[i],1,n,x,w);
}

ll Inquire(int x,int l,int r,int L,int R){
  if( x==0 ) return 0;
  if( L<=l && r<=R ) return Tr[x].v;
  ll res=0;
  if( L<=(l+r)/2 ) res+=Inquire(Tr[x].s[0],l,(l+r)/2,L,R);
  if( R>(l+r)/2 ) res+=Inquire(Tr[x].s[1],(l+r)/2+1,r,L,R);
  return res;
}

ll Query(int l,int r){
  ll res=0;
  for(int i=l;i<=n;i+=i&-i)
    res+=Inquire(bit[i],1,n,l,r);
  return res;
}

int main(){
#ifndef ONLINE_JUDGE
  freopen("E.in","r",stdin);
  freopen("E.out","w",stdout);
#endif
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
    if( link[a[i]] ) Modify(i,link[a[i]],i-link[a[i]]);
    link[a[i]]=i,Insert(root[a[i]],i,0);
  }
  for(int i=1;i<=m;i++){
    int op,x,y;
    scanf("%d%d%d",&op,&x,&y);
    if( op==1 ){
      if( a[x]==y ) continue;
      int pre=Find_pre(root[a[x]],x),sub=Find_sub(root[a[x]],x);
      if( pre!=0 ) Modify(x,pre,pre-x);
      if( sub!=n+1 ){
	Modify(sub,x,x-sub);
	if( pre!=0 ) Modify(sub,pre,sub-pre);
      }      
      if( Delete(root[a[x]],x) ){
	while( x ) printf("%d-%d-%d-%d-",x,a[x],tr[x].s[0],tr[x].s[1]),x=tr[x].par;
	return 0;
      }
      //Delete(root[a[x]],x);
      a[x]=y;
      Insert(root[y],x,0);
      
      pre=Find_pre(root[y],x),sub=Find_sub(root[y],x);
      if( pre!=0 ) Modify(x,pre,x-pre);
      if( sub!=n+1 ){
	if( pre!=0 ) Modify(sub,pre,pre-sub);
	Modify(sub,x,sub-x);
      }
    }
    else printf("%lld\n",Query(x,y));
  }
  //if( n==100000 ) printf("%d",size);
  return 0;
}
