#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int n, m, tot = 0, a[100000 + 5], last[100000 + 5], mark[100000 + 5];
long long Ans[100000 + 5], T[131072 * 2 + 5];
set<int> st[100000 + 5];
struct ques {
  int kind, x, y, v, ad, p;
} q[100000 * 7 + 5], s[100000 * 14 + 5];
bool cmp(const ques& a, const ques& b) {
  return a.p == b.p ? a.kind < b.kind : a.p < b.p;
}
void Renew(int x, int v) {
  for (T[x += 131072] += v, x >>= 1; x; x >>= 1)
    T[x] = T[x << 1] + T[x << 1 | 1];
}
long long Query(int l, int r) {
  long long sum = 0;
  for (l += 131072 - 1, r += 131072 + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
    if (~l & 1) sum += T[l + 1];
    if (r & 1) sum += T[r - 1];
  }
  return sum;
}
void Solve(int l, int r) {
  if (l == r) return;
  int mid = l + r >> 1, top = 0;
  Solve(l, mid);
  Solve(mid + 1, r);
  for (int i = l; i <= mid; ++i)
    if (!q[i].kind) s[++top] = q[i], s[top].p = s[top].x;
  for (int i = mid + 1; i <= r; ++i)
    if (q[i].kind == 1) {
      s[++top] = q[i];
      s[top].ad = -1;
      s[top].p = s[top].x - 1;
      s[++top] = q[i];
      s[top].ad = 1;
      s[top].p = s[top].y;
    }
  sort(s + 1, s + top + 1, cmp);
  for (int i = 1; i <= top; ++i)
    if (!s[i].kind)
      Renew(s[i].y, s[i].v);
    else
      Ans[s[i].v] += s[i].ad * Query(s[i].x, s[i].y);
  for (int i = 1; i <= top; ++i)
    if (!s[i].kind) Renew(s[i].y, -s[i].v);
}
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= n; ++i) {
    a[i] = read();
    if (last[a[i]]) q[++tot] = (ques){0, i, last[a[i]], i - last[a[i]]};
    last[a[i]] = i;
    st[a[i]].insert(i);
  }
  for (int i = 1; i <= m; ++i) {
    int op = read();
    if (op == 2) {
      int l = read(), r = read();
      q[++tot] = (ques){1, l, r, i, 0, 0};
      mark[i] = 1;
    } else {
      int x = read(), v = read(), f = 0;
      if (a[x] == v) continue;
      set<int>::iterator it = st[a[x]].lower_bound(x), it2;
      if (it != st[a[x]].begin()) {
        it2 = it;
        --it2;
        f = *it2;
        q[++tot] = (ques){0, x, f, -(x - f), 0, 0};
      }
      if (it2 = it, ++it2 != st[a[x]].end()) {
        q[++tot] = (ques){0, *it2, x, -(*it2 - x), 0, 0};
        if (f) q[++tot] = (ques){0, *it2, f, *it2 - f, 0, 0};
      }
      st[a[x]].erase(it);
      f = 0;
      a[x] = v;
      st[a[x]].insert(x);
      it = st[a[x]].lower_bound(x);
      if (it != st[a[x]].begin()) {
        it2 = it;
        --it2;
        f = *it2;
        q[++tot] = (ques){0, x, f, x - f, 0, 0};
      }
      if (it2 = it, ++it2 != st[a[x]].end()) {
        q[++tot] = (ques){0, *it2, x, *it2 - x, 0, 0};
        if (f) q[++tot] = (ques){0, *it2, f, -(*it2 - f), 0, 0};
      }
    }
  }
  Solve(1, tot);
  for (int i = 1; i <= m; ++i)
    if (mark[i]) printf("%lld\n", Ans[i]);
  return 0;
}
