#include <bits/stdc++.h>
using namespace std;
const double eps = 0.000000000000001;
unordered_map<int, long long> bit[100010];
set<int> s[100010];
int A[100010], lst[100010], n, q;
long long add[100010];
void upd(int id, int ind, int val) {
  while (id <= n) {
    int tmp = ind;
    while (tmp <= n) {
      bit[id][tmp] += val;
      tmp += (tmp & -tmp);
    }
    id += (id & -id);
  }
}
long long gotback(int id, int ind) {
  if (ind <= 0) return 0;
  static long long ret;
  unordered_map<int, long long>::iterator it;
  ret = 0;
  while (id > 0) {
    int tmp = ind;
    while (tmp > 0) {
      it = bit[id].find(tmp);
      if (it != bit[id].end()) ret += bit[id][tmp];
      tmp -= (tmp & -tmp);
    }
    id -= (id & -id);
  }
  return ret;
}
int main() {
  scanf("%d%d", &n, &q);
  int i, j;
  for (i = 1; i <= n; i++) {
    scanf("%d", &A[i]);
    if (lst[A[i]] > 0) {
      upd(i, lst[A[i]], i - lst[A[i]]);
      add[i] = i - lst[A[i]];
    }
    lst[A[i]] = i;
    s[A[i]].insert(i);
  }
  int typ, l, r, p, x;
  long long tobe = 0;
  set<int>::iterator it;
  while (q--) {
    scanf("%d", &typ);
    if (typ == 1) {
      scanf("%d%d", &p, &x);
      tobe = 0;
      it = s[A[p]].lower_bound(p);
      if (it == s[A[p]].begin()) {
        assert(add[p] == 0);
      } else {
        it--;
        upd(p, *it, -add[p]);
      }
      add[p] = 0;
      s[A[p]].erase(p);
      it = s[A[p]].lower_bound(p);
      if (it != s[A[p]].end()) {
        int ind = *it;
        if (add[ind] > 0) upd(ind, p, -add[ind]);
        add[ind] = 0;
        if (it != s[A[p]].begin()) {
          it--;
          upd(ind, *it, ind - *it);
          add[ind] = ind - *it;
        }
      }
      it = s[x].lower_bound(p);
      if (it != s[x].end()) {
        int ind = *it;
        if (it != s[x].begin()) {
          it--;
          upd(ind, *it, -add[ind]);
          add[ind] = 0;
        } else {
          assert(add[ind] == 0);
        }
        add[ind] = ind - p;
        upd(ind, p, add[ind]);
      }
      s[x].insert(p);
      A[p] = x;
      it = s[x].lower_bound(p);
      add[p] = 0;
      if (it != s[x].begin()) {
        it--;
        int prev = *it;
        add[p] = p - prev;
        upd(p, prev, add[p]);
      }
      assert(A[p] == x);
    } else {
      assert(typ == 2);
      scanf("%d%d", &l, &r);
      long long ans = gotback(r, n) - gotback(r, l - 1);
      printf("%lld\n", ans);
    }
  }
  return 0;
}
