#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, m, a[maxn];
set<int> s[maxn];
set<int>::iterator it;
namespace SGT {
unsigned T[maxn * 200];
int rt[maxn * 3], Ls[maxn * 200], Rs[maxn * 200], cur;
void pushup(int h) { T[h] = T[Ls[h]] + T[Rs[h]]; }
void updy(int& h, int l, int r, int p, unsigned w) {
  if (!h) h = ++cur;
  if (l == r) {
    T[h] += w;
    return;
  }
  if (p <= ((l + r) >> 1))
    updy(Ls[h], l, ((l + r) >> 1), p, w);
  else
    updy(Rs[h], ((l + r) >> 1) + 1, r, p, w);
  pushup(h);
}
void update(int h, int l, int r, int px, int py, unsigned w) {
  updy(rt[h], 1, n, py, w);
  if (l == r) return;
  if (px <= ((l + r) >> 1))
    update(h << 1, l, ((l + r) >> 1), px, py, w);
  else
    update(h << 1 | 1, ((l + r) >> 1) + 1, r, px, py, w);
}
unsigned qryy(int h, int l, int r, int L, int R) {
  if (L <= l && r <= R) return T[h];
  unsigned ret = 0;
  if (L <= ((l + r) >> 1)) ret += qryy(Ls[h], l, ((l + r) >> 1), L, R);
  if (R > ((l + r) >> 1)) ret += qryy(Rs[h], ((l + r) >> 1) + 1, r, L, R);
  return ret;
}
unsigned query(int h, int l, int r, int Lx, int Rx, int Ly, int Ry) {
  if (Lx <= l && r <= Rx) return qryy(rt[h], 1, n, Ly, Ry);
  unsigned ret = 0;
  if (Lx <= ((l + r) >> 1))
    ret += query(h << 1, l, ((l + r) >> 1), Lx, Rx, Ly, Ry);
  if (Rx > ((l + r) >> 1))
    ret += query(h << 1 | 1, ((l + r) >> 1) + 1, r, Lx, Rx, Ly, Ry);
  return ret;
}
}  // namespace SGT
using namespace SGT;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    if (!s[a[i]].empty()) {
      it = s[a[i]].end();
      int r = *(--it);
      update(1, 1, n, r, i, i - r);
    }
    s[a[i]].insert(i);
  }
  while (m--) {
    int op;
    scanf("%d", &op);
    if (op == 1) {
      int p, x, lst = 0, nxt = 0;
      scanf("%d%d", &p, &x);
      s[a[p]].erase(p);
      it = s[a[p]].lower_bound(p);
      if (it != s[a[p]].end()) {
        nxt = *it;
        update(1, 1, n, p, nxt, p - nxt);
      }
      if (it != s[a[p]].begin()) {
        lst = *(--it);
        update(1, 1, n, lst, p, lst - p);
      }
      if (lst && nxt) update(1, 1, n, lst, nxt, nxt - lst);
      lst = nxt = 0;
      a[p] = x;
      it = s[a[p]].lower_bound(p);
      if (it != s[a[p]].end()) {
        nxt = *it;
        update(1, 1, n, p, nxt, nxt - p);
      }
      if (it != s[a[p]].begin()) {
        lst = *(--it);
        update(1, 1, n, lst, p, p - lst);
      }
      if (lst && nxt) update(1, 1, n, lst, nxt, lst - nxt);
      s[a[p]].insert(p);
    } else {
      int l, r;
      scanf("%d%d", &l, &r);
      printf("%u\n", query(1, 1, n, l, r, 1, r));
    }
  }
  return 0;
}
