#include <bits/stdc++.h>
int n, a[100005];
namespace SegTree {
struct Node {
  Node *ch[2];
  long long sum;
  Node() {
    ch[0] = ch[1] = 0;
    sum = 0;
  }
  void update() {
    sum = 0;
    if (ch[0]) sum += ch[0]->sum;
    if (ch[1]) sum += ch[1]->sum;
  }
} * root[100005];
void modify(Node *&k, int l, int r, int pos, long long val) {
  if (!k) k = new Node();
  k->sum += val;
  if (l == r) {
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid)
    modify(k->ch[0], l, mid, pos, val);
  else
    modify(k->ch[1], mid + 1, r, pos, val);
}
long long query(Node *k, int l, int r, int L, int R) {
  if (!k) return 0;
  if (L <= l && r <= R) return k->sum;
  int mid = (l + r) >> 1;
  long long res = 0;
  if (L <= mid) res += query(k->ch[0], l, mid, L, R);
  if (mid < R) res += query(k->ch[1], mid + 1, r, L, R);
  return res;
}
void modify(int t, int pos, long long val) {
  for (int i = t; i <= n; i += ((i) & -(i))) modify(root[i], 0, n, pos, val);
}
long long query(int t, int l, int r) {
  long long res = 0;
  for (int i = t; i > 0; i -= ((i) & -(i))) res += query(root[i], 0, n, l, r);
  return res;
}
}  // namespace SegTree
std::set<int> col[100005];
int main() {
  static int m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", a + i);
    col[a[i]].insert(i);
  }
  for (int i = 1; i <= n; ++i) {
    int pre = 0;
    for (int x : col[i]) {
      SegTree::modify(x, pre, x - pre);
      pre = x;
    }
  }
  for (int i = 1; i <= n; ++i) col[i].insert(0);
  std::set<int>::iterator it;
  for (int pre, nxt, opt, x, y; m--;) {
    scanf("%d%d%d", &opt, &x, &y);
    if (opt == 1) {
      col[a[x]].erase(col[a[x]].find(x));
      pre = *--col[a[x]].lower_bound(x);
      SegTree::modify(x, pre, pre - x);
      it = col[a[x]].upper_bound(x);
      if (it != col[a[x]].end()) {
        nxt = *it;
        SegTree::modify(nxt, x, x - nxt);
        SegTree::modify(nxt, pre, nxt - pre);
      }
      col[y].insert(x);
      pre = *--col[y].lower_bound(x);
      SegTree::modify(x, pre, x - pre);
      it = col[y].upper_bound(x);
      if (it != col[y].end()) {
        nxt = *it;
        SegTree::modify(nxt, pre, pre - nxt);
        SegTree::modify(nxt, x, nxt - x);
      }
      a[x] = y;
    } else
      printf("%I64d\n", SegTree::query(y, x, y) - SegTree::query(x - 1, x, y));
  }
  return 0;
}
