#include <bits/stdc++.h>

using namespace std;

#define pii pair<int,int>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define int long long int

const int mx = 1e5+1 , rmx = 320, inf = 1e16;

int n, m, rn, a[mx];
int nx[mx], disnx[mx];

set<pii> s;

vector<pii> nxsort[rmx];    //  mp( nx , disnx )            //  i / rn  =   nod of i
int ps[rmx][rmx];

void loadnod(int nod)
{
    nxsort[nod].clear();
    for(int i=nod*rn ; i/rn==nod && i<n ; i++)
    {
        nxsort[nod].pb(mp(nx[i], disnx[i]));
    }

    sort(nxsort[nod].begin(), nxsort[nod].end());

    ps[nod][0] = nxsort[nod][0].ss;

    for(int i=1;i<nxsort[nod].size();i++)
    {
        ps[nod][i]=ps[nod][i-1]+nxsort[nod][i].ss;
    }
}

main()
{
    cin >> n >> m;
    rn = rmx;
    for(int i=0;i<n;i++)
    {
        cin >> a[i];
        s.insert(mp(a[i],i));
    }

    set<pii> :: iterator it;
    for(int i=0;i<n;i++)
    {
        it = s.lower_bound(mp(a[i],i));
        if(it!=s.end() && (++it)->ff == a[i])
        {
            nx[i] = it->ss;
            disnx[i] = nx[i]-i;
        }
        else
        {
            nx[i] = inf;
            disnx[i] = 0;
        }
    }

    for(int i=0;i*rn<n;i++)
        loadnod(i);

    int qt, l, r, p, x, L, R, mid;
    while(m--)
    {
        cin >> qt;
        if(qt==1)
        {
            cin >> p >> x;
            p--;
            if(a[p]==x)
                continue;
            it = s.lower_bound(mp(a[p],p));
            if(it!=s.begin() && (--it)->ff == a[p])
            {
                nx[it->ss] = nx[p];
                if(disnx[p]==0)
                    disnx[it->ss] = 0;
                else
                    disnx[it->ss] = nx[it->ss]-(it->ss);
                if((it->ss)/rn != p/rn)
                    loadnod((it->ss)/rn);
            }
            s.erase(mp(a[p],p));
            a[p] = x;
            s.insert(mp(a[p],p));
            it = s.lower_bound(mp(a[p],p));
            if(it!=s.end() && (++it)->ff == a[p])
            {
                nx[p] = it->ss;
                disnx[p] = nx[p]-p;
            }
            else
            {
                nx[p] = inf;
                disnx[p] = 0;
            }

            it = s.lower_bound(mp(a[p],p));
            if(it!=s.begin() && (--it)->ff == a[p])
            {
                nx[it->ss] = p;
                disnx[it->ss] = p-(it->ss);
                if((it->ss)/rn != p/rn)
                    loadnod((it->ss)/rn);
            }
            loadnod(p/rn);
        }

        if(qt==2)
        {
            cin >> l >> r;
            l--, r--;
            int ans = 0;
            if((r/rn) - (l/rn) <= 1)
            {
                for(int i=l;i<=r;i++)
                {
                    if(nx[i]<=r)
                    {
                        ans+=disnx[i];
                    }
                }
                cout << ans << '\n';
                continue;
            }
            for(int i=(l/rn)+1;i<(r/rn);i++)
            {
                if(nxsort[i][0].ff > r)
                    continue;
                L=0;
                R=nxsort[i].size();
                while(R-L>1)
                {
                    mid = (L+R)/2;
                    if(nxsort[i][mid].ff <= r)
                        L=mid;
                    else
                        R=mid;
                }
                ans+=ps[i][L];
            }

            for(int i=l ; i/rn == l/rn ;i++)
                if(nx[i]<=r)
                    ans += disnx[i];

            for(int i=r ; i/rn == r/rn ;i--)
                if(nx[i]<=r)
                    ans += disnx[i];

            cout << ans << '\n';
        }
    }
}



