#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
set<int> s[N];
int v[N], n, totq, sum[N];
long long ans[N];
struct oper {
  int a, b, id, ot;
  bool ty;
  oper(int a = 0, int b = 0, bool ty = 0, int ot = 0) {
    this->a = a, this->b = b, this->ty = ty;
    this->ot = ot;
  }
} o[N];
inline int pre(int x) {
  if (s[v[x]].find(x) == s[v[x]].begin()) return 0;
  return *--s[v[x]].find(x);
}
inline int nxt(int x) {
  auto it = s[v[x]].find(x);
  if (it == --s[v[x]].end()) return x;
  return *++it;
}
inline bool cmp1(oper a, oper b) { return a.a + a.b < b.a + b.b; }
inline bool cmp2(oper a, oper b) { return a.b < b.b; }
inline void ins(int x, int y) {
  for (int i = x; i <= n; i += i & -i) sum[i] += y;
}
inline long long que(int x) {
  long long ans = 0;
  for (int i = x; i; i -= i & -i) ans += sum[i];
  return ans;
}
void CDQ(int l, int r) {
  if (l == r) return;
  int m = l + r >> 1, tl = l;
  CDQ(l, m), CDQ(m + 1, r);
  sort(o + l, o + m + 1, cmp1), sort(o + m + 1, o + r + 1, cmp2);
  for (int i = m + 1; i <= r; ++i) {
    while (tl <= m && o[tl].a + o[tl].b <= o[i].b) {
      if (o[tl].ty) ins(o[tl].a, o[tl].ot * o[tl].b);
      ++tl;
    }
    if (!o[i].ty) ans[o[i].id] += que(o[i].b) - que(o[i].a - 1);
  }
  for (int i = l; i < tl; ++i) {
    if (o[i].ty) ins(o[i].a, -o[i].ot * o[i].b);
  }
  return;
}
int main() {
  int m;
  cin >> n >> m;
  int totp = 0;
  for (int i = 1; i <= n; ++i) scanf("%d", &v[i]), s[v[i]].insert(i);
  int totq = 0;
  for (int i = 1; i <= n; ++i) o[++totq] = oper(i, nxt(i) - i, 1, 1);
  for (int i = 1; i <= m; ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    --a;
    if (a)
      o[++totq] = oper(b, c, 0), o[totq].id = ++totp;
    else {
      int d = pre(b), e = nxt(b);
      o[++totq] = oper(b, e - b, 1, -1);
      if (d)
        o[++totq] = oper(d, b - d, 1, -1),
        o[++totq] = oper(d, e == b ? 0 : e - d, 1, 1);
      s[v[b]].erase(b);
      s[v[b] = c].insert(b);
      d = pre(b);
      e = nxt(b);
      o[++totq] = oper(b, e - b, 1, 1);
      if (d)
        o[++totq] = oper(d, e == b ? 0 : e - d, 1, -1),
        o[++totq] = oper(d, b - d, 1, 1);
    }
  }
  CDQ(1, totq);
  for (int i = 1; i <= totp; ++i) printf("%lld\n", ans[i]);
  return 0;
}
