#include <bits/stdc++.h>
using namespace std;
int n, m;
int tot, fla[500001];
int a[500001], nxt[500001], pre[500001], po[500001];
long long ans[500001], c[50001];
set<int> s[100001];
struct Query {
  int op, y, z, v, id;
} Q[1000001];
inline void mk(int op, int y, int z, int v, int id) {
  Q[++tot].y = y, Q[tot].z = z;
  Q[tot].id = id;
  Q[tot].op = op;
  Q[tot].v = v;
}
inline int lowbit(int x) { return x & (-x); }
inline void add(int x, int d) {
  for (int i = x; i <= 100005; i += lowbit(i)) c[i] += d;
}
inline long long sum(int x) {
  long long ret = 0;
  for (int i = x; i; i -= lowbit(i)) ret += c[i];
  return ret;
}
inline bool cmp(Query x, Query y) { return x.y < y.y; }
inline void CDQ(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  CDQ(l, mid);
  CDQ(mid + 1, r);
  sort(Q + l, Q + mid + 1, cmp);
  sort(Q + mid + 1, Q + r + 1, cmp);
  int pos = l;
  for (int i = mid + 1; i <= r; i++) {
    while (pos <= mid && Q[pos].y <= Q[i].y) {
      if (Q[pos].op == 0) add(Q[pos].z + 1, Q[pos].v);
      pos++;
    }
    if (Q[i].op == 1) ans[Q[i].id] += sum(Q[i].z + 1);
  }
  for (int i = l; i < pos; i++) {
    if (Q[i].op == 0) add(Q[i].z + 1, -(Q[i].v));
  }
}
inline int read() {
  int ln = 0;
  char ch = getchar();
  while (ch < '0') ch = getchar();
  while (ch >= '0') {
    ln = (ln << 3) + (ln << 1) + ch - '0';
    ch = getchar();
  }
  return ln;
}
int main() {
  n = read(), m = read();
  for (int i = 1; i <= n; i++) {
    s[i].insert(0);
    s[i].insert(n + 1);
    a[i] = read();
    pre[i] = po[a[i]];
    po[a[i]] = i;
    mk(0, i, pre[i], i - pre[i], 0);
    s[a[i]].insert(i);
  }
  for (int i = 1; i <= n; i++) po[i] = n + 1;
  for (int i = n; i >= 1; i--) {
    nxt[i] = po[a[i]];
    po[a[i]] = i;
  }
  for (int i = 1, op, x, y; i <= m; i++) {
    op = read(), x = read(), y = read();
    if (op == 1) {
      if (a[x] == y) continue;
      mk(0, x, pre[x], pre[x] - x, 0);
      mk(0, nxt[x], x, x - nxt[x], 0);
      mk(0, nxt[x], pre[x], nxt[x] - pre[x], 0);
      nxt[pre[x]] = nxt[x];
      pre[nxt[x]] = pre[x];
      s[a[x]].erase(x);
      a[x] = y;
      s[y].insert(x);
      set<int>::iterator Nw = s[y].find(x);
      int Pr = *(--Nw), Nx = *(++(++(Nw)));
      mk(0, Nx, Pr, Pr - Nx, 0);
      mk(0, x, Pr, x - Pr, 0);
      mk(0, Nx, x, Nx - x, 0);
      pre[Nx] = nxt[Pr] = x;
      pre[x] = Pr, nxt[x] = Nx;
    } else {
      mk(1, x - 1, x - 1, 0, i * 4 - 3);
      mk(1, x - 1, y, 0, i * 4 - 2);
      mk(1, y, x - 1, 0, i * 4 - 1);
      mk(1, y, y, 0, i * 4);
      fla[i] = 1;
    }
  }
  CDQ(1, tot);
  for (int i = 1; i <= m; i++) {
    if (fla[i])
      printf("%lld\n",
             ans[i * 4 - 3] - ans[i * 4 - 2] - ans[i * 4 - 1] + ans[i * 4]);
  }
  return 0;
}
