                 //       ONLY FOR KING RAHMANI MASTER OF DP       \\

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#define int long long
#define lb(a) ((a)&(-a))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
using namespace __gnu_pbds;
using namespace std;

const int maxn=2e5+11,maxm=50+11,mod=1e9+7;

int tp,l1,r1,q,a[maxn],n,t,sq=1000,ans;

int  fen[maxm][maxn];

int fen1[maxm][maxn];

set <int> ss[maxn];

set <int> ::iterator it,it1;

void ad(int pos,int x,int id)
{
    pos+=5;
    for(;pos<(maxn);pos+=lb(pos))
    {
        fen[id][pos]+=x;
    }
}

void ad1(int pos,int x,int id)
{
    pos+=5;
    for(;pos<(maxn);pos+=lb(pos))
    {
        fen1[id][pos]+=x;
    }
}

int get(int l,int r,int id)
{
    int ans5;
    for(r+=5;r>0;r-=lb(r))
    {
        ans5-=fen[id][r];
    }
    for(int i=((maxn)-1);i>0;i-=lb(i))
    {
        ans5+=fen[id][i];
    }
    for(l+=4;l>0;l-=lb(l))
    {
        ans5+=fen1[id][l];
    }
    return ans5;
}

int32_t main()
{
  //  ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  //    1103 1097 1193 10087 10133 11021 1119 10007
  //  cout<<setprecision(9);
  //  cout<<std::fixed;
    scanf("%d%d",&n,&q);
    for(int i=0;i<maxn;i++)
    {
        ss[i].insert(0);
        ss[i].insert(n+1);
    }
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        ss[a[i]].insert(i+1);
    }
    for(int i=0;i<n;i++)
    {
        it=ss[a[i]].lower_bound(i+1);
        it--;
        ad1(*it,-(i+1),i/sq);
        it++;
        it++;
        ad(*it,i+1,i/sq);
    }
    while(q--)
    {
        ans=0;
        scanf("%d%d%d",&tp,&l1,&r1);
        if(tp==1)
        {
            l1--;
            if(a[l1]!=r1)
            {
                int x=a[l1];
                it=ss[x].lower_bound(l1+1);
                it--;
                it1=it;
                it1++;
                it1++;
                ad(*it1,-(l1+1),l1/sq);
                ad1(*it,l1+1,l1/sq);
                if(*it!=0)
                {
                    ad(l1+1,-(*it),((*it)-1)/sq);
                    ad(*it1,(*it),((*it)-1)/sq);
                }
                if(*it1!=n+1)
                {
                    ad1(l1+1,(*it1),((*it1)-1)/sq);
                    ad1(*it,-(*it1),((*it1)-1)/sq);
                }
                ss[x].erase(l1+1);
                ss[r1].insert(l1+1);
                a[l1]=r1;
                it=ss[r1].lower_bound(l1+1);
                it1=it;
                it--;
                it1++;
                ad(*it1,l1+1,l1/sq);
                ad1(*it,-(l1+1),l1/sq);
                if(*it!=0)
                {
                    ad(l1+1,(*it),((*it)-1)/sq);
                    ad(*it1,-(*it),((*it)-1)/sq);
                }
                if(*it1!=n+1)
                {
                    ad1(l1+1,-(*it1),((*it1)-1)/sq);
                    ad1(*it,(*it1),((*it1)-1)/sq);
                }
            }
        }
        else{
            l1--;
            r1--;
            if(r1-l1<1000)
            {
                for(int i=l1;i<=r1;i++)
                {
                    it=ss[a[i]].lower_bound(i+1);
                it1=it;
                it--;
                it1++;
                if(*it1>(r1+1))
                    ans+=(i+1);
                if(*it<(l1+1))
                    ans-=(i+1);
             //     cout<<ans<<' '<<i<<endl;
                }

            }
            else{
            int ll=l1/sq,rr=r1/sq;
            for(int i=ll+1;i<rr;i++)
            {
                ans+=get(l1,r1,i);
            }
            for(int i=l1;i<(ll*sq);i++)
            {
                it=ss[a[i]].lower_bound(i+1);
                it1=it;
                it--;
                it1++;
                if(*it1>r1+1)
                    ans+=i+1;
                if(*it<l1+1)
                    ans-=i+1;
            }

            for(int i=(rr*sq);i<=r1;i++)
            {
                it=ss[a[i]].lower_bound(i+1);
                it1=it;
                it--;
                it1++;
                if(*it1>r1+1)
                    ans+=i+1;
                if(*it<l1+1)
                    ans-=i+1;
            }
            }
          //  cout<<endl;
            printf("%d\n",ans);
           // cout<<endl;
        }
    }
	return 0;
}
