#include <bits/stdc++.h>
using std::cerr;
using std::endl;
const int N = 1e6 + 233;
int n, m, val[N], qwq[N];
long long ans[N];
std::set<int> set[N];
struct Node {
  int t, l, r, val;
} op[N], buc[N];
int tot;
long long bit[N];
inline void add(int x, int y) {
  for (; x <= n; x += x & -x) bit[x] += y;
}
inline long long ask(int x) {
  if (x <= 0) return 0;
  long long ret = 0;
  for (; x; x -= x & -x) ret += bit[x];
  return ret;
}
void cdq(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  cdq(l, mid), cdq(mid + 1, r);
  int ql = l, qr = mid + 1, p = l - 1;
  while (ql <= mid || qr <= r) {
    if ((qr > r) || (ql <= mid && op[ql].l >= op[qr].l)) {
      if (op[ql].t >= 0) add(op[ql].r, op[ql].val);
      buc[++p] = op[ql++];
    } else {
      if (op[qr].t < 0) ans[-op[qr].t] += ask(op[qr].r);
      buc[++p] = op[qr++];
    }
  }
  for (int i = l; i <= mid; ++i)
    if (op[i].t >= 0) add(op[i].r, -op[i].val);
  for (int i = l; i <= r; ++i) op[i] = buc[i];
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", val + i);
    int pre = i;
    if (!set[val[i]].empty()) pre = *set[val[i]].rbegin();
    set[val[i]].insert(i);
    op[++tot] = {0, pre, i, i - pre};
  }
  for (int i = 1; i <= m; ++i) {
    int o;
    scanf("%d", &o);
    if (o == 1) {
      int x, y;
      scanf("%d %d", &x, &y);
      int pre = x, nxt = x;
      if (!set[val[x]].empty() && *set[val[x]].begin() < x)
        pre = *--set[val[x]].lower_bound(x);
      if (!set[val[x]].empty() && *set[val[x]].rbegin() > x)
        nxt = *set[val[x]].upper_bound(x);
      op[++tot] = {i, pre, x, pre - x};
      op[++tot] = {i, x, nxt, x - nxt};
      if (!set[y].empty() && *set[y].begin() < x && *set[y].rbegin() > x) {
        pre = *--set[y].lower_bound(x);
        nxt = *set[y].upper_bound(x);
        op[++tot] = {i, pre, nxt, pre - nxt};
      }
      set[val[x]].erase(x), val[x] = y;
      pre = nxt = x;
      if (!set[val[x]].empty() && *set[val[x]].begin() < x)
        pre = *--set[val[x]].lower_bound(x);
      if (!set[val[x]].empty() && *set[val[x]].rbegin() > x)
        nxt = *set[val[x]].upper_bound(x);
      op[++tot] = {i, pre, x, x - pre};
      op[++tot] = {i, x, nxt, nxt - x};
    } else {
      int l, r;
      scanf("%d %d", &l, &r);
      op[++tot] = {-i, l, r, 0};
      qwq[i] = 1;
    }
  }
  cdq(1, tot);
  for (int i = 1; i <= m; ++i)
    if (qwq[i]) printf("%lld\n", ans[i]);
  return 0;
}
