#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
#define ll long long
#define ull  unsigned long long
#define pb push_back

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 110000;
int nxt[N], d[N], a[N], used[N], B[N];
int n;
const int b = 350;
pair < int, int > c[500][500];
int s[500][500];
set < int > ms[N];
void build(){
    memset(d, 0, sizeof(d));
    memset(nxt, 0, sizeof(nxt));
    for (int i = 1; i <= n; i++){
        if (d[a[i]] != 0){
            nxt[d[a[i]]] = i;
        }
        d[a[i]] = i;
    }
    for (int i = 1; i <= n; i++) if (nxt[i] == 0) nxt[i] = n + 1;
    for (int i = 1; i + b <= n + 1; i += b){
        int k = i / b;
        for (int j = i; j < i + b; j++){
            c[k][j - i + 1].F = nxt[j];
            c[k][j - i + 1].S = nxt[j] - j;
        }
        sort(c[k] + 1, c[k] + b + 1);
        for (int j = 1; j <= b; j++){
            s[k][j] = s[k][j - 1] + c[k][j].S;
        }
    }
}
int solve(int x, int l, int r){
    //cout << x << " " << l << " " << r << endl;
    if (ms[x].size() == 0) return 0;
    auto it1 = ms[x].lower_bound(l);
    auto it2 = ms[x].upper_bound(r);
    it2--;
    if (it1 == ms[x].end()){
       // cout << 0 << endl;
        return 0;
    }
    int L = (*it1);
    int R = (*it2);
    //cout << max(0, R - L) << endl;
    return max(0, R - L);
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt",  "r", stdin);
    //freopen("output.txt", "w", stdout);
    int m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        ms[a[i]].insert(i);
    }
    build();
    vector < pair < int, int > > v;
    for (int i = 1; i <= m; i++){
        int type;
        cin >> type;
        if (type == 1){
            int p, x;
            cin >> p >> x;
            v.pb({p, x});
            B[p] = x;
        }
        if (v.size() > b){
            for (auto i: v){
                ms[a[i.F]].erase(i.F);
                a[i.F] = i.S;
                ms[a[i.F]].insert(i.F);
            }
            build();
            v.clear();
        }
        if (type == 2){
            int l, r;
            int ans = 0;
            cin >> l >> r;
            int l0 = l;
            int r0 = r;
            while(l % b != 1 && l < r){
                if (nxt[l] <= r) ans += nxt[l] - l;
                l++;
            }
            while(r % b && r > l){
                if (nxt[r] <= r0) ans += nxt[r] - r;
                r--;
            }
            //cout << ans << " " << l << " " << r << endl;
            for (int i = l / b; i < r / b; i++){
                int L = 0;
                int R = b + 1;
               // cout << i << " <- i" << " " << c[i][1].F << endl;
                while(R - L > 1){
                    int mid = (R + L) / 2;
                    if (c[i][mid].F > r0){
                        R = mid;
                    } else{
                        L = mid;
                    }
                }
                //cout << L << endl;
                ans += s[i][L];
            }
            l = l0;
            r = r0;
           // cout << ans << endl;
            for (auto i: v){
                if (B[i.F] != i.S) continue;
                if (used[a[i.F]]) continue;
                ans -= solve(a[i.F], l, r);
                used[a[i.F]] = 1;
            }for (auto i: v){
                if (B[i.F] != i.S) continue;
                if (used[i.S]) continue;
                ans -= solve(i.S, l, r);
                used[i.S] = 1;
            }
            for (auto i: v){
                if (B[i.F] != i.S) continue;
                ms[a[i.F]].erase(i.F);
                ms[i.S].insert(i.F);
                used[a[i.F]] = 0;
                used[i.S] = 0;
            }
            for (auto i: v){
                if (B[i.F] != i.S) continue;
                if (used[a[i.F]]) continue;
                ans += solve(a[i.F], l, r);
                used[a[i.F]] = 1;
            }for (auto i: v){
                if (B[i.F] != i.S) continue;
                if (used[i.S]) continue;
                ans += solve(i.S, l, r);
                used[i.S] = 1;
            }
            for (auto i: v){
                if (B[i.F] != i.S) continue;
                ms[a[i.F]].insert(i.F);
                ms[i.S].erase(i.F);
                used[a[i.F]] = 0;
                used[i.S] = 0;
            }
            cout << ans << endl;
        }
    }
}
