#include <bits/stdc++.h>
const int maxn = 1e5 + 5;
int n, m, q, a[maxn], qcnt;
std ::set<int> occur[maxn];
long long ans[maxn];
struct Sta {
  int ty, op, qid, x, y;
  Sta(){};
  Sta(int a, int b, int c, int d, int e) : ty(a), op(b), qid(c), x(d), y(e){};
} p[maxn * 14], tmp[maxn * 14];
struct BIT {
  long long c[maxn];
  void upd(int x, int v) {
    ++x;
    for (; x <= n + 2; x += (x & (-x))) c[x] += v;
  }
  long long sum(int x) {
    ++x;
    long long res = 0;
    for (; x; x -= (x & (-x))) res += c[x];
    return res;
  }
} bit;
void cdq(int l, int r) {
  if (l == r) return;
  int mid = l + r >> 1, i, j, cnt = 0;
  cdq(l, mid), cdq(mid + 1, r);
  for (i = mid + 1, j = l; i <= r; ++i) {
    while (j <= mid && p[j].x < p[i].x) {
      if (p[j].ty == 0) bit.upd(p[j].y, p[j].x * p[j].op);
      ++j;
    }
    if (p[i].ty == 2) ans[p[i].qid] += p[i].op * bit.sum(p[i].y - 1);
  }
  for (i = l; i < j; ++i)
    if (p[i].ty == 0) bit.upd(p[i].y, -p[i].x * p[i].op);
  for (i = mid + 1, j = l; i <= r; ++i) {
    while (j <= mid && p[j].x < p[i].x) {
      if (p[j].ty == 1) bit.upd(p[j].y, p[j].x * p[j].op);
      ++j;
    }
    if (p[i].ty == 3)
      ans[p[i].qid] += p[i].op * (bit.sum(n + 1) - bit.sum(p[i].y));
  }
  for (i = l; i < j; ++i)
    if (p[i].ty == 1) bit.upd(p[i].y, -p[i].x * p[i].op);
  for (i = mid + 1, j = l; i <= r; ++i) {
    while (j <= mid && p[j].x < p[i].x) tmp[++cnt] = p[j], ++j;
    tmp[++cnt] = p[i];
  }
  while (j <= mid) tmp[++cnt] = p[j], ++j;
  for (i = 1; i <= cnt; ++i) p[i + l - 1] = tmp[i];
}
int main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; ++i) occur[i].insert(0), occur[i].insert(n + 1);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), occur[a[i]].insert(i);
  for (int i = 1; i <= n; ++i) {
    p[++m] = Sta(0, 1, 0, i, *(--occur[a[i]].find(i)));
    p[++m] = Sta(1, 1, 0, i, *(++occur[a[i]].find(i)));
  }
  for (int i = 1, ty, b, c, pre, suf; i <= q; ++i) {
    scanf("%d %d %d", &ty, &b, &c);
    if (ty == 1) {
      pre = *(--occur[a[b]].find(b)), suf = *(++occur[a[b]].find(b));
      p[++m] = Sta(0, -1, 0, b, pre);
      p[++m] = Sta(1, -1, 0, b, suf);
      if (suf != n + 1)
        p[++m] = Sta(0, -1, 0, suf, b), p[++m] = Sta(0, 1, 0, suf, pre);
      if (pre != 0)
        p[++m] = Sta(1, -1, 0, pre, b), p[++m] = Sta(1, 1, 0, pre, suf);
      occur[a[b]].erase(b), a[b] = c, occur[a[b]].insert(b);
      pre = *(--occur[a[b]].find(b)), suf = *(++occur[a[b]].find(b));
      if (suf != n + 1)
        p[++m] = Sta(0, -1, 0, suf, pre), p[++m] = Sta(0, 1, 0, suf, b);
      if (pre != 0)
        p[++m] = Sta(1, -1, 0, pre, suf), p[++m] = Sta(1, 1, 0, pre, b);
      p[++m] = Sta(0, 1, 0, b, pre);
      p[++m] = Sta(1, 1, 0, b, suf);
    }
    if (ty == 2) {
      ++qcnt;
      p[++m] = Sta(2, 1, qcnt, b, b), p[++m] = Sta(2, -1, qcnt, c + 1, b);
      p[++m] = Sta(3, -1, qcnt, b, c), p[++m] = Sta(3, 1, qcnt, c + 1, c);
    }
  }
  cdq(1, m);
  for (int i = 1; i <= qcnt; ++i) printf("%lld\n", ans[i]);
  return 0;
}
