#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MaxN = 1e6 + 55;
const int K = sqrt(MaxN);
const int INF = 1e9;
const int MOD = 1e9 + 7;

int n, m;

int a[MaxN];
int b[MaxN];

int WHAT[MaxN];

long long added[MaxN];

int type[MaxN];
int q[MaxN];
int w[MaxN];
int lastPos[MaxN];

long long sum[MaxN];
long long pref[MaxN];
long long suf[MaxN];

long long sumPref[MaxN];
long long sumSuf[MaxN];

set<int> s[MaxN];

vector <pair<int, int> > vector1;
vector <pair<pair<int, int>, int > > vector2;

void addElem(int pos, int x)
{
    s[b[pos]].erase(pos);
    b[pos] = x;
    s[b[pos]].insert(pos);
}

void make()
{
    memset(lastPos, 0, sizeof(lastPos));
    memset(sum, 0, sizeof(sum));
    memset(suf, 0, sizeof(suf));
    memset(pref, 0, sizeof(pref));

    for(int i = 1; i <= n; ++i)
    {
        s[i].clear();
        s[i].insert(0);
        s[i].insert(n + 1);
    }

    for(int i = 1; i <= n; ++i)
    {
        s[a[i]].insert(i);
        b[i] = a[i];

        pref[i] = 0;
        if(lastPos[a[i]])
        {
            vector1.push_back(make_pair(lastPos[a[i]], i));
            pref[i] = i - lastPos[a[i]];
            sum[i] += pref[i];
        }
        lastPos[a[i]] = i;
    }

    memset(lastPos, 0, sizeof(lastPos));

    for(int i = n; i > 0; --i)
    {
        suf[i] = 0;
        if(lastPos[a[i]])
        {
            suf[i] = lastPos[a[i]] - i;
            sum[i] += suf[i];
        }
        lastPos[a[i]] = i;
    }

    memset(lastPos, 0, sizeof(lastPos));

    long long cur = 0;

    for(int i = 1; i <= n; ++i)
    {
        if(lastPos[a[i]])
            cur -= suf[lastPos[a[i]]];
        cur += suf[i];
        sumPref[i] = cur;
        lastPos[a[i]] = i;
    }

    memset(lastPos, 0, sizeof(lastPos));

    cur = 0;

    for(int i = n; i; --i)
    {
        if(lastPos[a[i]])
            cur -= pref[lastPos[a[i]]];
        cur += pref[i];
        sumSuf[i] = cur;
        lastPos[a[i]] = i;
    }

    for(int i = 1; i <= n; ++i)
        sum[i] += sum[i - 1];
}



struct Tree{

    long long t[MaxN * 4];

    Tree()
    {
        for(int i = 0; i < MaxN * 4; ++i)
            t[i] = 0;
    }

    void clear()
    {
        for(int i = 0; i < MaxN * 4; ++i)
            t[i] = 0;
    }

    void up(int x, int l, int r, int pos, int delta)
    {
        t[x] += delta;
        if(l == r)
            return;
        int mid = (l + r) / 2;
        if(mid >= pos)
            up(x + x, l, mid, pos, delta);
        else
            up(x + x + 1, mid + 1, r, pos, delta);
    }
    void up(int pos, int delta)
    {
        up(1, 1, MaxN - 1, pos, delta);
    }
    long long get(int x, int l, int r, int ll, int rr)
    {
        if(l > rr || r < ll)
            return 0;
        if(l >= ll && r <= rr)
            return t[x];
        int mid = (l + r) / 2;
        return get(x + x, l, mid, ll, rr) + get(x + x + 1, mid + 1, r, ll, rr);
    }
    long long get(int l, int r)
    {
        return get(1, 1, MaxN - 1, l, r);
    }
} tree;

struct pof{
    int pos, type, vType, number;
    pof()
    {
        pos = type = vType = number = 0;
    }
    pof(int pos, int type, int vType, int number) : pos(pos), type(type), vType(vType), number(number)
    {

    }
    bool operator < (const pof & oth) const
    {
        return (pos < oth.pos) || (pos == oth.pos && type < oth.type) || (pos == oth.pos && type == oth.type && vType < oth.vType) ||
        (pos == oth.pos && type == oth.type && vType == oth.vType && number < oth.number);
    }
};

void makeAll()
{
    tree.clear();

    vector <pof> pofs;

    for(int i = 0; i < vector1.size(); ++i)
    {
        pofs.push_back(pof(vector1[i].first, 0, 0, vector1[i].second));
        pofs.push_back(pof(vector1[i].second, 1, 0, vector1[i].first));
    }
    for(int i = 0; i < vector2.size(); ++i)
    {
        pofs.push_back(pof(vector2[i].first.first, -2, vector2[i].first.second, vector2[i].second));
    }

    sort(pofs.begin(), pofs.end());

    int l = 0;
    while(l < pofs.size())
    {
        int r = l + 1;
        while(r < pofs.size() && pofs[l].pos == pofs[r].pos)
            ++r;

        for(int i = l; i < r; ++i)
            if(pofs[i].type == -2)
            {
                added[pofs[i].number] = tree.get(pofs[i].vType + 1, MaxN - 1);
                //tree.up(pofs[i].number, pofs[i].number - pofs[i].pos);
            }

        for(int i = l; i < r; ++i)
            if(pofs[i].type == 0)
            {
                tree.up(pofs[i].number, pofs[i].number - pofs[i].pos);
            }
        l = r;
    }

}

void del(long long & ans, int pos, int l, int r)
{
    if(pos < l || pos > r)
        return;
    int x = b[pos];
    set<int> :: iterator it1 = s[x].lower_bound(pos);
    set<int> :: iterator it2 = s[x].upper_bound(pos);
    --it1;
    int nPos = (*it2);
    int pPos = (*it1);

    if(nPos <= r && pPos >= l)
        return;
    if(nPos > r && pPos < l)
        return;

    if(nPos <= r)
    {
        ans -= nPos - pos;
    }else
    {
        ans -= pos - pPos;
    }
}

void add(long long & ans, int pos, int l, int r)
{
    if(pos < l || pos > r)
        return;
    int x = b[pos];
    set<int> :: iterator it1 = s[x].lower_bound(pos);
    set<int> :: iterator it2 = s[x].upper_bound(pos);

    --it1;
    int nPos = (*it2);
    int pPos = (*it1);

    if(nPos <= r && pPos >= l)
        return;
    if(nPos > r && pPos < l)
        return;
    if(nPos <= r)
    {
        ans += nPos - pos;
    }else
    {
        ans += pos - pPos;
    }
}

main()
{
//    freopen("input.txt", "r", stdin);
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    for(int i = 1; i <= m; ++i)
        cin >> type[i] >> q[i] >> w[i];

    int l = 1;



    while(l <= m)
    {
        make();
        int r = min(m, l + K - 1);

        for(int i = l; i <= r; ++i)
            if(type[i] == 2)
                vector2.push_back(make_pair(make_pair(q[i], w[i]), i));

        makeAll();

        for(int i = l; i <= r; ++i)
        {
            if(type[i] == 2)
            {
                int L = q[i];
                int R = w[i];
                long long ans = sum[R] - sum[L - 1] - sumPref[L - 1] - sumSuf[R + 1] + added[i] * 2ll;
                //cout << ans << '\n';
                ans /= 2;
                //cout << ans << '\n';
                for(int j = l; j < i; ++j)
                    if(type[j] == 1)
                    {
                        WHAT[j] = b[q[j]];
                        int curPos = q[j];
                        int curX = w[j];
                        del(ans, curPos, L, R);
                        addElem(curPos, curX);
                        add(ans, curPos, L, R);
                    }

                cout << ans << '\n';

                for(int j = i - 1; j >= l; --j)
                    if(type[j] == 1)
                    {
                        addElem(q[j], WHAT[j]);
                    }
            }
        }

        for(int i = l; i <= r; ++i)
            if(type[i] == 1)
                a[q[i]] = w[i];

        l += K;
    }



    return 0;
}
