#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline T read() {
  register T sum = 0;
  register char cc = getchar();
  int sym = 1;
  while (cc != '-' && (cc > '9' || cc < '0')) cc = getchar();
  if (cc == '-') sym = -1, cc = getchar();
  sum = sum * 10 + cc - '0';
  cc = getchar();
  while (cc >= '0' && cc <= '9') sum = sum * 10 + cc - '0', cc = getchar();
  return sym * sum;
}
template <typename T>
inline T read(T &a) {
  a = read<T>();
  return a;
}
template <typename T, typename... Others>
inline void read(T &a, Others &...b) {
  a = read(a);
  read(b...);
}
struct Data {
  int op;
  int a, b, c;
  bool operator<(const Data &o) const { return a < o.a; }
} a[100010 * 8];
int n, m, l, Q, b[100010], pre[100010], nxt[100010], las[100010];
long long t[100010], ans[100010];
set<int> s[100010];
int lowbit(int x) { return x & -x; }
void add(int x, int y) {
  for (int i = x; i <= n; i += lowbit(i)) t[i] += y;
}
long long query(int x) {
  if (!x) return 0;
  long long res = 0;
  for (int i = x; i; i -= lowbit(i)) res += t[i];
  return res;
}
void CDQ(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  CDQ(l, mid);
  CDQ(mid + 1, r);
  sort(a + l, a + mid + 1);
  sort(a + mid + 1, a + r + 1);
  int j = l;
  for (int i = mid + 1; i <= r; i++) {
    while (j <= mid && a[j].a <= a[i].a) {
      if (!a[j].op) add(a[j].b, a[j].c);
      j += 1;
    }
    if (a[i].op) ans[a[i].c] += query(n) - query(a[i].b - 1);
  }
  for (int i = l; i < j; i++)
    if (!a[i].op) add(a[i].b, -a[i].c);
}
int main() {
  read(n, m);
  for (int i = 1; i <= n; i++) {
    read(b[i]);
    if (las[b[i]]) {
      pre[i] = las[b[i]];
      nxt[las[b[i]]] = i;
      a[++l] = {0, i, las[b[i]], i - las[b[i]]};
    }
    las[b[i]] = i;
    s[b[i]].insert(i);
  }
  for (int i = 1; i <= m; i++) {
    int x, y, z;
    read(x, y, z);
    if (x == 1) {
      if (pre[y]) {
        a[++l] = {0, y, pre[y], -(y - pre[y])};
        nxt[pre[y]] = nxt[y];
      }
      if (nxt[y]) {
        a[++l] = {0, nxt[y], y, -(nxt[y] - y)};
        pre[nxt[y]] = pre[y];
      }
      if (pre[y] && nxt[y]) a[++l] = {0, nxt[y], pre[y], nxt[y] - pre[y]};
      s[b[y]].erase(y);
      b[y] = z;
      auto it = s[z].upper_bound(y);
      nxt[y] = it == s[z].end() ? 0 : *it;
      pre[y] = it == s[z].begin() ? 0 : *(--it);
      s[b[y]].insert(y);
      if (nxt[y]) {
        if (pre[nxt[y]])
          a[++l] = {0, nxt[y], pre[nxt[y]], -(nxt[y] - pre[nxt[y]])};
        pre[nxt[y]] = y;
        a[++l] = {0, nxt[y], y, nxt[y] - y};
      }
      if (pre[y]) {
        a[++l] = {0, y, pre[y], y - pre[y]};
        nxt[pre[y]] = y;
      }
    } else {
      Q += 1;
      a[++l] = {1, z, y, Q};
    }
  }
  CDQ(1, l);
  for (int i = 1; i <= Q; i++) printf("%lld\n", ans[i]);
  return 0;
}
