#include <bits/stdc++.h>
using namespace std;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
const int N = int(1e5) + 10;
const int B = 1000;
const int LOGN = 20;
int L[2][N * LOGN], R[2][N * LOGN];
long long int ST[2][N * LOGN];
int blen[2], root[2][N], A[N], t;
inline int update(int pos, int add, int l, int r, int id) {
  if (l > pos || r <= pos) return id;
  int ID = ++blen[t], m = l + (r - l) / 2;
  if (l == r - 1) return (ST[t][ID] = ST[t][id] + add, ID);
  L[t][ID] = update(pos, add, l, m, L[t][id]);
  R[t][ID] = update(pos, add, m, r, R[t][id]);
  return (ST[t][ID] = ST[t][L[t][ID]] + ST[t][R[t][ID]], ID);
}
inline long long int query(int L, int R, int l, int r, int x) {
  if (l >= L && r <= R) return ST[t][x];
  if (l >= R || r <= L) return 0;
  if (!x) return 0;
  int mid = (l + r) >> 1;
  return query(L, R, l, mid, ::L[t][x]) + query(L, R, mid, r, ::R[t][x]);
}
int done[N], prv[N], nxt[N], pos[N], newprv[N], newnxt[N];
pair<int, int> updates[N];
set<int> val[N];
void process(int n) {
  memset(pos, 0, sizeof(pos));
  for (int i = 1; i <= n; i++) {
    prv[i] = pos[A[i]];
    pos[A[i]] = i;
  }
  memset(pos, 0, sizeof(pos));
  for (int i = n; i >= 1; i--) {
    nxt[i] = pos[A[i]];
    pos[A[i]] = i;
  }
  blen[0] = blen[1] = 0;
  t = 0;
  root[t][0] = ++blen[t];
  for (int i = 1; i <= n; i++) {
    root[t][i] = update(prv[i], -prv[i], 1, N, root[t][i - 1]);
    root[t][i] = update(i, i, 1, N, root[t][i]);
  }
  t = 1;
  root[t][n + 1] = ++blen[t];
  for (int i = n; i >= 1; i--) {
    root[t][i] = update(nxt[i], -nxt[i], 1, N, root[t][i + 1]);
    root[t][i] = update(i, i, 1, N, root[t][i]);
  }
}
int main() {
  int n;
  scanf("%d", &n);
  int m;
  scanf("%d", &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &A[i]);
    val[A[i]].insert(i);
  }
  int ulen = 0;
  process(n);
  for (int i = 1; i <= m; i++) {
    if (i % B == 0) {
      process(n);
      ulen = 0;
    }
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int p, x;
      scanf("%d", &p);
      scanf("%d", &x);
      auto it = val[A[p]].lower_bound(p);
      int pr = 0, nx = 0;
      if (it != val[A[p]].begin()) {
        auto it2 = it;
        it2--;
        pr = *it2;
      }
      if (++it != val[A[p]].end()) {
        nx = *it;
      }
      newnxt[pr] = nx;
      newprv[nx] = pr;
      val[A[p]].erase(p);
      updates[++ulen] = {p, x};
      val[x].insert(p);
      A[p] = x;
      it = val[x].lower_bound(p);
      if (it != val[x].begin()) {
        auto it2 = it;
        it2--;
        newprv[p] = *it2;
      }
      if (++it != val[x].end()) {
        newnxt[p] = *it;
      }
    } else {
      int l, r;
      scanf("%d", &l);
      scanf("%d", &r);
      ::t = 0;
      long long int ans = query(l, r + 1, 1, N, root[::t][r]);
      ::t = 1;
      ans -= query(l, r + 1, 1, N, root[::t][l]);
      auto f = [&l, &r](int x) { return x >= l && x <= r; };
      for (int j = ulen; j >= 1; j--) {
        int p = updates[j].first;
        if (!f(p) || done[p]) continue;
        done[p] = 1;
        if (f(prv[p]) && f(nxt[p])) {
        } else if (f(prv[p])) {
          ans -= (p - prv[p]);
        } else if (f(nxt[p])) {
          ans -= (nxt[p] - p);
        }
        if (f(newnxt[p]) && f(newprv[p])) {
        } else if (f(newprv[p])) {
          ans += (p - newprv[p]);
        } else if (f(newnxt[p])) {
          ans += (newnxt[p] - p);
        }
      }
      for (int j = 1; j <= ulen; ++j) done[updates[j].first] = 0;
      printf("%lld\n", ans);
    }
  }
  return 0;
}
