#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 10;
long long n, m, a[N];
set<long long> ps[N];
namespace Seg {
const long long xb = N - 5;
const long long S = 10 * N * 20;
signed c[S][2];
unsigned size, sm[S];
struct InnerSeg {
  signed rt;
  InnerSeg() : rt(0) {}
  inline void Add(long long x, long long y, signed &v, long long l = 0,
                  long long r = n + 1) {
    if (!v) v = ++size;
    sm[v] += y;
    if (l == r) return;
    long long mid = (l + r) >> 1;
    if (x <= mid)
      Add(x, y, c[v][0], l, mid);
    else
      Add(x, y, c[v][1], mid + 1, r);
  }
  inline long long Ask(long long x, long long y, long long v, long long l = 0,
                       long long r = n + 1) {
    if (!v || l > y || r < x) return 0;
    if (x <= l && r <= y) return sm[v];
    long long mid = (l + r) >> 1;
    return Ask(x, y, c[v][0], l, mid) + Ask(x, y, c[v][1], mid + 1, r);
  }
} f[N << 1];
inline void Add(long long x, long long y, long long z) {
  for (long long i = xb + x; i; i >>= 1) f[i].Add(y, z, f[i].rt);
}
inline long long Ask(long long x, long long y) {
  long long ans = 0;
  for (long long l = xb + x - 1, r = xb + n + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
    if (~l & 1) ans += f[l ^ 1].Ask(1, y, f[l ^ 1].rt);
    if (r & 1) ans += f[r ^ 1].Ask(1, y, f[r ^ 1].rt);
  }
  return ans;
}
}  // namespace Seg
signed main() {
  scanf("%lld%lld", &n, &m);
  for (long long i = 1; i <= n; ++i) ps[i].insert(0);
  for (long long i = 1; i <= n; ++i) {
    scanf("%lld", a + i);
    if (*--ps[a[i]].end())
      Seg::Add(*--ps[a[i]].end(), i, i - *--ps[a[i]].end());
    ps[a[i]].insert(i);
  }
  for (long long i = 1; i <= n; ++i) ps[i].insert(n + 1);
  for (long long i = 1, opt, x, y; i <= m; ++i) {
    scanf("%lld%lld%lld", &opt, &x, &y);
    if (opt == 1) {
      if (a[x] == y) continue;
      set<long long>::iterator it = ps[a[x]].find(x);
      long long u = *prev(it), v = *it, w = *next(it);
      if (u) Seg::Add(u, v, -(v - u));
      if (w != n + 1) Seg::Add(v, w, -(w - v));
      if (u && w != n + 1) Seg::Add(u, w, w - u);
      ps[a[x]].erase(it);
      it = ps[a[x] = y].insert(x).first;
      u = *prev(it), v = *it, w = *next(it);
      if (u) Seg::Add(u, v, v - u);
      if (w != n + 1) Seg::Add(v, w, w - v);
      if (u && w != n + 1) Seg::Add(u, w, -(w - u));
    } else {
      printf("%lld\n", Seg::Ask(x, y));
    }
  }
  return 0;
}
