#include <bits/stdc++.h>   using namespace std;   int const N = 1e5 + 13;   int const INF = 1e9 + 13;   int n, m;   set<int> p[N];   int l[N], r[N];   int pos[N], x[N];   int tsz;   int a[N];   int type[N];   vector<int> t[N * 4], tright[N * 4];   vector<long long> F[N * 4];   vector<int> qid;   vector<pair<int, int>> qpos[N];   vector<int> lposes;   bool cmpl(int i, int j) { return l[i] < l[j]; }   void merge(vector<int> &v, vector<int> &l, vector<int> &r) {     int lp = 0;     int rp = 0;     int ln = l.size();     int rn = r.size();     while (lp < ln || rp < rn) {       if (rp == rn || (lp < ln && ::r[l[lp]] < ::r[r[rp]])) {         v.push_back(l[lp++]);       } else {         v.push_back(r[rp++]);       }     }   }   void build(int v, int tl, int tr) {     if (tl == tr) {       t[v].push_back(qid[tl]);       F[v].assign(1, 0LL);       for (int i = 0; i < t[v].size(); ++i) {         qpos[t[v][i]].push_back(make_pair(v, i));       }       tright[v].push_back(r[qid[tl]]);     } else {       int tm = (tl + tr) / 2;       build(v * 2 + 1, tl, tm);       build(v * 2 + 2, tm + 1, tr);       merge(t[v], t[v * 2 + 1], t[v * 2 + 2]);       for (int i = 0; i < t[v].size(); ++i) {         qpos[t[v][i]].push_back(make_pair(v, i));         tright[v].push_back(r[t[v][i]]);       }       F[v].assign(t[v].size(), 0LL);     }   }   void updF(vector<long long> &F, int x, int v) {     int n = F.size();     while (x < n) {       F[x] += v;       x |= (x + 1);     }   }   long long getF(vector<long long> &F, int x) {     long long res = 0;     while (x >= 0) {       res += F[x];       x = (x & (x + 1)) - 1;     }     return res;   }   void upd(vector<long long> &F, int l, int r, int val) {     if (l > r) return;     updF(F, l, val);     updF(F, r + 1, -val);   }   int getLeft(vector<int> &v, int val) {     int l = -1;     int r = v.size();     while (r - l > 1) {       int m = (l + r) / 2;       if (v[m] >= val)         r = m;       else         l = m;     }     return r;   }   int getRight(vector<int> &v, int val) {     int l = -1;     int r = v.size();     while (r - l > 1) {       int m = (l + r) / 2;       if (v[m] <= val)         l = m;       else         r = m;     }     return l;   }   void upd(int v, int tl, int tr, int ll, int lr, int rl, int rr, int val) {     if (tl > lr || ll > tr) return;     if (ll <= tl && tr <= lr) {       int left = getLeft(tright[v], rl);       int right = getRight(tright[v], rr);       upd(F[v], left, right, val);       return;     }     int tm = (tl + tr) / 2;     upd(v * 2 + 1, tl, tm, ll, lr, rl, rr, val);     upd(v * 2 + 2, tm + 1, tr, ll, lr, rl, rr, val);   }   long long answer(int id) {     long long res = 0;     for (int i = 0; i < qpos[id].size(); ++i) {       res += getF(F[qpos[id][i].first], qpos[id][i].second);     }     return res;   }   void push(int pos, int val) {     set<int>::iterator bef, aft;     bef = p[val].lower_bound(pos);     aft = p[val].upper_bound(pos);     if (bef != p[val].begin()) {       --bef;       int lp = (*bef);       int dist = pos - lp;       lp = getRight(lposes, lp);       int rp = (aft == p[val].end() ? INF : (*aft) - 1);       upd(0, 0, tsz - 1, 0, lp, pos, rp, dist);     }     bef = p[val].lower_bound(pos);     aft = p[val].upper_bound(pos);     if (aft != p[val].end()) {       int lp;       if (bef != p[val].begin()) {         --bef;         lp = (*bef) + 1;       } else {         lp = 0;       }       lp = getLeft(lposes, lp);       int rp = getRight(lposes, pos);       int rpp = (*aft);       int dist = rpp - pos;       upd(0, 0, tsz - 1, lp, rp, rpp, INF, dist);     }     p[val].insert(pos);   }   void pop(int pos, int val) {     p[val].erase(pos);     set<int>::iterator bef, aft;     bef = p[val].lower_bound(pos);     aft = p[val].upper_bound(pos);     if (bef != p[val].begin()) {       --bef;       int lp = (*bef);       int dist = pos - lp;       lp = getRight(lposes, lp);       int rp = (aft == p[val].end() ? INF : (*aft) - 1);       upd(0, 0, tsz - 1, 0, lp, pos, rp, -dist);     }     bef = p[val].lower_bound(pos);     aft = p[val].upper_bound(pos);     if (aft != p[val].end()) {       int lp;       if (bef != p[val].begin()) {         --bef;         lp = (*bef) + 1;       } else {         lp = 0;       }       lp = getLeft(lposes, lp);       int rp = getRight(lposes, pos);       int rpp = (*aft);       int dist = rpp - pos;       upd(0, 0, tsz - 1, lp, rp, rpp, INF, -dist);     }   }   void solve() {     cin >> n >> m;     for (int i = 0; i < n; ++i) cin >> a[i];     for (int i = 0; i < m; ++i) {       cin >> type[i];       if (type[i] == 1) {         cin >> pos[i] >> x[i];         --pos[i];       } else {         cin >> l[i] >> r[i];         --l[i];         --r[i];         qid.push_back(i);       }     }     tsz = qid.size();     if (tsz == 0) return;     sort(qid.begin(), qid.end(), cmpl);     for (int i = 0; i < qid.size(); ++i) lposes.push_back(l[qid[i]]);     build(0, 0, tsz - 1);     for (int i = 0; i < n; ++i) push(i, a[i]);     for (int i = 0; i < m; ++i) {       if (type[i] == 1) {         pop(pos[i], a[pos[i]]);         a[pos[i]] = x[i];         push(pos[i], a[pos[i]]);       } else {         long long ans = answer(i);         cout << ans << endl;       }     }   }   int main() {     solve();     return 0;   }   