#include <bits/stdc++.h>
using namespace std;
struct SegmentTree {
  struct Node {
    Node *lch, *rch;
    long long sum;
    Node() {
      lch = rch = nullptr;
      sum = 0;
    }
    void up() {
      sum = 0;
      if (lch != nullptr) sum += lch->sum;
      if (rch != nullptr) sum += rch->sum;
    }
  } * root;
  SegmentTree() { root = nullptr; }
  void modify(int l, int r, int pos, int v, Node*& node) {
    if (node == nullptr) node = new Node();
    if (l == r) {
      node->sum += v;
    } else {
      int mid = (l + r) >> 1;
      if (pos <= mid)
        modify(l, mid, pos, v, node->lch);
      else
        modify(mid + 1, r, pos, v, node->rch);
      node->up();
    }
  }
  long long query(int l, int r, int ql, int qr, Node* node) {
    if (node == nullptr) return 0;
    if (l == ql && r == qr) return node->sum;
    int mid = (l + r) >> 1;
    if (qr <= mid)
      return query(l, mid, ql, qr, node->lch);
    else if (ql > mid)
      return query(mid + 1, r, ql, qr, node->rch);
    else
      return query(l, mid, ql, mid, node->lch) +
             query(mid + 1, r, mid + 1, qr, node->rch);
  }
} bit[100010];
int n;
inline int lowbit(int x) { return x & -x; }
inline void modify(int x, int y, int v) {
  for (int i = x; i <= n; i += lowbit(i))
    bit[i].modify(0, n, y, v, bit[i].root);
}
inline long long query(int pos, int ql, int qr) {
  long long res = 0;
  for (int i = pos; i > 0; i -= lowbit(i))
    res += bit[i].query(0, n, ql, qr, bit[i].root);
  return res;
}
inline long long Query(int xl, int xr, int yl, int yr) {
  return query(xr, yl, yr) - query(xl - 1, yl, yr);
}
set<int> pos[100010];
int a[100010];
int main() {
  int m, op, p, x, l, r;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) pos[i].insert(0);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    auto it = pos[a[i]].end();
    it--;
    modify(i, *it, i - *it);
    pos[a[i]].insert(i);
  }
  while (m--) {
    scanf("%d", &op);
    if (op == 1) {
      scanf("%d%d", &p, &x);
      auto it = pos[a[p]].find(p), it2 = it;
      it2--;
      it++;
      modify(p, *it2, -(p - *it2));
      if (it != pos[a[p]].end()) {
        modify(*it, p, -(*it - p));
        modify(*it, *it2, *it - *it2);
      }
      pos[a[p]].erase(p);
      a[p] = x;
      pos[x].insert(p);
      it = pos[x].find(p), it2 = it;
      it2--;
      it++;
      modify(p, *it2, p - *it2);
      if (it != pos[x].end()) {
        modify(*it, *it2, -(*it - *it2));
        modify(*it, p, *it - p);
      }
    } else {
      scanf("%d%d", &l, &r);
      printf("%lld\n", Query(l, r, l, r));
    }
  }
  return 0;
}
