#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
inline long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
struct s {
  int opt, l, r, v;
};
s e[1000000], tmp[1000000];
int all, n, m;
int a[100050];
long long ans[100050];
inline void aq(int a, int b, int c, int d) { e[++all] = (s){a, b, c, d}; }
long long c[100050];
void add(int x, long long dt) {
  for (; x <= n; x += x & -x) c[x] += dt;
}
long long sum(int x) {
  long long ret = 0;
  for (; x; x -= x & -x) ret += c[x];
  return ret;
}
void cdq(int l, int r) {
  if (l == r) return;
  int mid = (l + r) / 2;
  cdq(l, mid), cdq(mid + 1, r);
  for (int i = l, j = mid + 1, idx = l; idx <= r; idx++) {
    if (i <= mid && e[i].l >= e[j].l || j > r) {
      if (e[i].opt == 0) add(e[i].r, e[i].v);
      tmp[idx] = e[i++];
    } else {
      if (e[j].opt) {
        ans[e[j].opt] += sum(e[j].r);
      }
      tmp[idx] = e[j++];
    }
  }
  for (int i = (l); i <= (int)(mid); i++)
    if (e[i].opt == 0) add(e[i].r, -e[i].v);
  copy(tmp + l, tmp + r + 1, e + l);
}
set<int> S[100050];
void init() {}
int main() {
  cin >> n >> m;
  for (int i = (1); i <= (int)(n); i++) {
    a[i] = read();
    S[a[i]].insert(i);
  }
  for (int i = (1); i <= (int)(n); i++) {
    int last = 0;
    for (auto p : S[i]) {
      if (last == 0) {
        last = p;
        continue;
      }
      aq(0, last, p, p - last);
      last = p;
    }
  }
  int qq = 0;
  for (int i = (1); i <= (int)(m); i++) {
    int opt = read(), b = read(), c = read();
    if (opt == 1) {
      if (a[b] == c) continue;
      int le = 0, ri = 0;
      auto it = S[a[b]].lower_bound(b);
      if (it != S[a[b]].begin()) le = *(--it), ++it;
      if (++it != S[a[b]].end()) ri = *it;
      if (le) aq(0, le, b, -(b - le));
      if (ri) aq(0, b, ri, -(ri - b));
      if (le && ri) aq(0, le, ri, ri - le);
      S[a[b]].erase(b);
      le = ri = 0;
      it = S[c].lower_bound(b);
      if (it != S[c].begin()) le = *(--it), ++it;
      if (it != S[c].end()) ri = *it;
      if (le && ri) aq(0, le, ri, -(ri - le));
      if (le) aq(0, le, b, b - le);
      if (ri) aq(0, b, ri, ri - b);
      S[c].insert(b);
      a[b] = c;
    } else {
      aq(++qq, b, c, 0);
    }
  }
  cdq(1, all);
  for (int i = (1); i <= (int)(qq); i++) printf("%lld\n", ans[i]);
  return 0;
}
