#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int n, m, cnt, tot;
int a[N], vis[N];
unsigned int Ans[N], b[N];
set<int> s[N];
struct node {
  int opt, l, r, w;
} que[N * 7], q[N * 7];
inline void modify(int p, int v) {
  for (; p <= n; p += p & -p) b[p] += v;
}
inline int query(int p, int r = 0) {
  for (; p; p ^= p & -p) r += b[p];
  return r;
}
void solve(int l, int r) {
  int flag = 0;
  for (int i = l; i <= r; ++i)
    if (que[i].opt == 2) flag = 1;
  if (!flag || l == r) return;
  const int mid = l + r >> 1;
  solve(l, mid);
  solve(mid + 1, r);
  tot = 0;
  for (int i = l; i <= mid; ++i)
    if (que[i].opt == 1) q[++tot] = que[i];
  for (int i = mid + 1; i <= r; ++i)
    if (que[i].opt == 2) q[++tot] = que[i];
  sort(q + 1, q + tot + 1, [](const node &a, const node &b) {
    return a.r == b.r ? a.opt < b.opt : a.r < b.r;
  });
  for (int i = 1; i <= tot; ++i)
    if (q[i].opt == 1)
      modify(q[i].l, q[i].w);
    else
      Ans[q[i].w] += query(n) - query(q[i].l - 1);
  for (int i = 1; i <= tot; ++i)
    if (q[i].opt == 1) modify(q[i].l, -q[i].w);
}
inline int read(register int x = 0, register char ch = getchar(),
                register int f = 0) {
  for (; !isdigit(ch); ch = getchar()) f = ch == '-';
  for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
  return f ? -x : x;
}
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= n; ++i) a[i] = read(), s[a[i]].insert(i);
  for (int i = 1; i <= n; ++i)
    if (s[i].size() > 1)
      for (auto it = s[i].begin(); next(it) != s[i].end(); ++it)
        que[++cnt] = (node){1, *it, *next(it), *next(it) - *it};
  for (int i = 1, opt, l, r; i <= m; ++i) {
    opt = read();
    l = read();
    r = read();
    if (opt == 1) {
      auto it = s[a[l]].find(l);
      if (it != s[a[l]].begin())
        que[++cnt] = (node){1, *prev(it), *it, -*it + *prev(it)};
      if (next(it) != s[a[l]].end())
        que[++cnt] = (node){1, *it, *next(it), -*next(it) + *it};
      if (it != s[a[l]].begin() && next(it) != s[a[l]].end())
        que[++cnt] = (node){1, *prev(it), *next(it), *next(it) - *prev(it)};
      s[a[l]].erase(it);
      a[l] = r;
      it = s[a[l]].insert(l).first;
      if (it != s[a[l]].begin())
        que[++cnt] = (node){1, *prev(it), *it, *it - *prev(it)};
      if (next(it) != s[a[l]].end())
        que[++cnt] = (node){1, *it, *next(it), *next(it) - *it};
      if (it != s[a[l]].begin() && next(it) != s[a[l]].end())
        que[++cnt] = (node){1, *prev(it), *next(it), -*next(it) + *prev(it)};
    } else
      que[++cnt] = (node){2, l, r, i};
  }
  solve(1, cnt);
  for (int i = 1; i <= cnt; ++i)
    if (que[i].opt == 2) printf("%u\n", Ans[que[i].w]);
  return 0;
}
