#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fio ios_base::sync_with_stdio(false)
#define MOD 1000000007
#define INF 1000000000
#define INFLL 1000000000000000000ll
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define long int64_t
using namespace std;
using namespace __gnu_pbds;
typedef pair<int, int> pii;
typedef priority_queue<pii, vector<pii>, greater<pii>> min_pq;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> OST;

template<class Node_CItr, class Node_Itr, class Cmp_Fn, class _Alloc> struct pst_node_update
{
    typedef long metadata_type;

    long ps(int v)
    {
        long ret = 0;
        auto it = node_begin();
        while(it != node_end())
        {
            auto l = it.get_l_child();
            auto r = it.get_r_child();
            if(greater<int>()(v, (*it)->ff))
                it = r;
            else
            {
                ret += it.get_metadata();
                it = l;
            }
        }
        return ret;
    }

    void operator()(Node_Itr it, Node_CItr end_it)
    {
        auto r = it.get_r_child();
        long right = 0;
        if(r != end_it)
            right = r.get_metadata();
        const_cast<metadata_type &>(it.get_metadata()) = right + (*it)->ss;
    }

    virtual Node_CItr
    node_begin() const = 0;
 
    virtual Node_CItr
    node_end() const = 0;
};

typedef tree<pii, null_type, less<pii>, rb_tree_tag, pst_node_update> PST;

const int N = 100001;

int a[N];
PST bit[N];
set<int> s[N];

void del(pii v, int p)
{
    while(p < N)
    {
        bit[p].erase(v);
        p += p & -p;
    }
}

void add(pii v, int p)
{
    while(p < N)
    {
        bit[p].insert(v);
        p += p & -p;
    }
}

long query(int p, int v)
{
    long ret = 0;
    while(p)
    {
        ret += bit[p].ps(v);
        p -= p & -p;
    }
    return ret;
}

int main()
{
    fio;
    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i];
        if(s[a[i]].empty())
            add(mp(0, i), i);
        else
            add(mp(*(s[a[i]].rbegin()), i - *(s[a[i]].rbegin())), i);
        s[a[i]].insert(i);
    }
    while(m--)
    {
        int ty, l, r;
        cin >> ty >> l >> r;
        if(ty == 1)
        {
            auto it = s[a[l]].find(l);
            int pl = 0;
            if(it != s[a[l]].begin())
            {
                it--;
                pl = *it;
                it++;
            }
            del(mp(pl, l-pl), l);
            it++;
            if(it != s[a[l]].end())
            {
                del(mp(l, *it-l), *it);
                add(mp(pl, *it-pl), *it);
            }
            it--;
            s[a[l]].erase(it);
            it = s[r].insert(l).ff;
            pl = 0;
            if(it != s[r].begin())
            {
                it--;
                pl = *it;
                it++;
            }
            add(mp(pl, l-pl), l);
            it++;
            if(it != s[r].end())
            {
                add(mp(l, *it-l), *it);
                del(mp(pl, *it-pl), *it);
            }
            a[l] = r;
        }
        else
        {
            long ans = query(r, l);
            cout << ans << endl;
        }
    }
    return 0;
}