#include <bits/stdc++.h>   using namespace std;   const long double eps = 1e-9;   long double PI = acos((long double)-1.0);   struct io_s {     bool negative;     char ch;     inline bool isdigitx(char c) { return c >=  0  && c <=  9 ; }     inline char nextchar() {       static char buf[100000], *p1 = buf, *p2 = buf;       return p1 == p2 &&                      (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)                  ? EOF                  : *p1++;     }     template <typename T>     bool rn(T& _v) {       negative = false;       _v = 0;       while (!isdigitx(ch = nextchar()) && ch != EOF) {         negative = ch ==  - ;       };       if (ch == EOF) return false;       do {         _v *= 10;         _v += ch -  0 ;       } while (isdigitx(ch = nextchar()));       if (negative) _v = -_v;       return true;     }     template <typename T>     bool run(T& _v) {       _v = 0;       while (!isdigitx(ch = nextchar()) && ch != EOF) {       };       if (ch == EOF) return false;       do {         _v *= 10;         _v += ch -  0 ;       } while (isdigitx(ch = nextchar()));       return true;     }     template <typename T>     inline T r() {       T v = T();       rn(v);       return v;     }     inline int ri() { return r<int>(); }     inline long long rll() { return r<long long>(); }     inline int gets(char* s) {       char* c = s;       do {         ch = nextchar();       } while (ch ==   n  || ch ==   r );       do {         *(c++) = ch;         ch = nextchar();       } while (ch !=   n  && ch !=   r );       *(c++) =   0 ;       return c - s - 1;     }     inline char get() {       do {         ch = nextchar();       } while (ch <  A  || ch >  Z );       return ch;     }     template <class T>     inline void o(T p) {       static int stk[70], tp;       if (p == 0) {         putchar( 0 );         return;       }       if (p < 0) {         p = -p;         putchar( - );       }       while (p) stk[++tp] = p % 10, p /= 10;       while (tp) putchar(stk[tp--] +  0 );     }     inline void ln() { putchar(  n ); }     inline void space() { putchar(   ); }     template <class T>     inline void oln(T p) {       o(p);       ln();     }   } io;   using namespace std;   const int N = 100005, M = 10000005;   int ls[M], rs[M], rt[N], n, a[N], m, ndc;   set<int> dat[N];   long long sum[M];   void update(int& x, int l, int r, int p, int u) {     if (!x) x = ++ndc;     sum[x] += u;     if (l == r) return;     int mid = (l + r) >> 1;     if (p <= mid)       update(ls[x], l, mid, p, u);     else       update(rs[x], mid + 1, r, p, u);   }   long long ask(int& x, int l, int r, int s, int t) {     if (!x || l == s && r == t) return sum[x];     int mid = (l + r) >> 1;     if (t <= mid) return ask(ls[x], l, mid, s, t);     if (s > mid) return ask(rs[x], mid + 1, r, s, t);     return ask(ls[x], l, mid, s, mid) + ask(rs[x], mid + 1, r, mid + 1, t);   }   void modify(int x, int y, int u) {     while (x <= n) update(rt[x], 1, n, y, u), x += ((x) & -(x));   }   long long query(int x, int y) {     long long ret = 0;     while (x) ret += ask(rt[x], 1, n, 1, y), x &= x - 1;     return ret;   }   void add(int p, int x) {     dat[p].insert(x);     auto it = dat[p].find(x), pre = it, suf = it;     bool f1 = false, f2 = false;     if (pre != dat[p].begin()) --pre, modify(*pre, x, x - *pre), f1 = 1;     ++suf;     if (suf != dat[p].end()) modify(x, *suf, *suf - x), f2 = 1;     if (f1 && f2) modify(*pre, *suf, -(*suf - *pre));   }   void del(int p, int x) {     auto it = dat[p].find(x), pre = it, suf = it;     bool f1 = false, f2 = false;     if (pre != dat[p].begin()) --pre, modify(*pre, x, -(x - *pre)), f1 = 1;     ++suf;     if (suf != dat[p].end()) modify(x, *suf, -(*suf - x)), f2 = 1;     if (f1 && f2) modify(*pre, *suf, *suf - *pre);     dat[p].erase(x);   }   int main() {     io.rn(n);     io.rn(m);     for (int i = 1; i <= n; i++) add(a[i] = io.ri(), i);     for (int i = 1, o, u, v; i <= m; i++) {       io.rn(o);       io.rn(u);       io.rn(v);       if (o == 1)         del(a[u], u), a[u] = v, add(a[u], u);       else {         int t = n;         while (t > 0 && (t & (t - 1)) >= v - 1) t &= (t - 1);         io.oln(query(t, v) - query(u - 1, v));       }     }     return 0;   }   