#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5;
struct node {
  int l, r, t, v, id;
  friend bool operator<(node a, node b) {
    if (a.l != b.l) return a.l > b.l;
    if (a.t != b.t) return a.t < b.t;
    return a.r < b.r;
  }
} p[maxn * 3];
int cnt, n, m, a[maxn], c[maxn], ans[maxn], ac, typ[maxn];
set<int> s[maxn];
void add(int x, int v) {
  while (x <= n) c[x] += v, x += x & (-x);
}
int ask(int x) {
  int sum = 0;
  while (x) sum += c[x], x -= x & (-x);
  return sum;
}
void cdq(int l, int r) {
  if (l == r) return;
  int mid = (l + r) / 2, lst = l;
  cdq(l, mid), cdq(mid + 1, r);
  sort(p + l, p + mid + 1), sort(p + mid + 1, p + r + 1);
  for (register int i = mid + 1; i <= r; i++) {
    while (p[lst].l >= p[i].l && lst <= mid) add(p[lst].r, p[lst].v), lst++;
    ans[p[i].id] += ask(p[i].r);
  }
  for (register int i = l; i < lst; i++) add(p[i].r, -p[i].v);
}
int main() {
  int op, x, y;
  scanf("%d%d", &n, &m);
  for (register int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    if (s[a[i]].size())
      p[++cnt] = (node){*(--s[a[i]].end()), i}, p[cnt].v = p[cnt].r - p[cnt].l;
    s[a[i]].insert(i);
  }
  for (register int i = 1; i <= m; i++) {
    scanf("%d%d%d", &op, &x, &y);
    if (op == 2) {
      p[++cnt] = (node){x, y, i, 0, ++ac};
      continue;
    }
    int c = a[x], pd1 = 0, pd2 = 0;
    set<int>::iterator it = s[c].lower_bound(x), tmp = s[c].upper_bound(x);
    if (it != s[c].begin())
      p[++cnt] = (node){*(--it), x, i}, p[cnt].v = p[cnt].l - p[cnt].r, pd1 = 1,
      typ[cnt] = 1;
    if (tmp != s[c].end())
      p[++cnt] = (node){x, *tmp, i}, p[cnt].v = p[cnt].l - p[cnt].r, pd2 = 1,
      typ[cnt] = 2;
    if (pd1 && pd2) {
      cnt++;
      p[cnt] = (node){p[cnt - 2].l, p[cnt - 1].r, i},
      p[cnt].v = p[cnt].r - p[cnt].l, typ[cnt] = 3;
    }
    pd1 = pd2 = 0;
    s[c].erase(x);
    tmp = it = s[y].lower_bound(x);
    if (tmp != s[y].begin())
      p[++cnt] = (node){*(--tmp), x, i}, p[cnt].v = p[cnt].r - p[cnt].l,
      pd1 = 1, typ[cnt] = 4;
    if (it != s[y].end())
      p[++cnt] = (node){x, *it, i}, p[cnt].v = p[cnt].r - p[cnt].l, pd2 = 1,
      typ[cnt] = 5;
    if (pd1 && pd2) {
      cnt++;
      p[cnt] = (node){p[cnt - 2].l, p[cnt - 1].r, i},
      p[cnt].v = p[cnt].l - p[cnt].r, typ[cnt] = 6;
    }
    s[y].insert(x);
    a[x] = y;
  }
  cdq(1, cnt);
  for (register int i = 1; i <= ac; i++) printf("%d\n", ans[i]);
  return 0;
}
