#include <bits/stdc++.h>
using namespace std;
int n, m, tot, cnt, p[100100], ans[100100], q[100100], sum[100100];
set<int> s[100100];
struct point {
  int t, y, x, w;
  friend bool operator<(point a, point b) { return a.x > b.x; }
} a[100100 * 8];
void add(int x, int y) {
  while (x <= n) sum[x] += y, x += x & (-x);
}
int query(int x, int ret = 0) {
  while (x) ret += sum[x], x -= x & (-x);
  return ret;
}
void CDQ(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1, j = l;
  CDQ(l, mid);
  CDQ(mid + 1, r);
  sort(a + l, a + mid + 1);
  sort(a + mid + 1, a + r + 1);
  for (int i = mid + 1; i <= r; i++) {
    while (a[j].x >= a[i].x && j <= mid) add(a[j].y, a[j].w), j++;
    ans[a[i].t] += query(a[i].y);
  }
  for (int i = l; i < j; ++i) add(a[i].y, -a[i].w);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1, x, lst, w; i <= n; i++) {
    scanf("%d", &x);
    p[i] = x;
    s[x].insert(i);
    set<int>::iterator it = s[x].lower_bound(i);
    if (it != s[x].begin())
      it--, lst = (*it), w = i - lst;
    else
      lst = w = 0;
    a[++tot] = (point){0, i, lst, w};
  }
  for (int i = 1; i <= m; i++) {
    int opt, x, y;
    scanf("%d%d%d", &opt, &x, &y);
    if (opt == 1) {
      set<int>::iterator it = s[p[x]].lower_bound(x);
      int lst = 0, nxt = 0, w;
      if (it != s[p[x]].begin())
        it--, lst = (*it), w = x - lst;
      else
        lst = w = 0;
      a[++tot] = (point){i, x, lst, -w};
      it = s[p[x]].lower_bound(x);
      if (it != (--s[p[x]].end()))
        it++, nxt = (*it), a[++tot] = (point){i, nxt, x, x - nxt};
      if (lst && nxt) a[++tot] = (point){i, nxt, lst, nxt - lst};
      s[p[x]].erase(x);
      p[x] = y;
      lst = nxt = 0;
      s[y].insert(x);
      it = s[y].lower_bound(x);
      if (it != (--s[p[x]].end())) nxt = (*(++it)), --it;
      if (it != s[p[x]].begin()) lst = (*(--it)), ++it;
      if (lst && nxt) a[++tot] = (point){i, nxt, lst, lst - nxt};
      if (lst) a[++tot] = (point){i, x, lst, x - lst};
      if (nxt) a[++tot] = (point){i, nxt, x, nxt - x};
    } else
      a[++tot] = (point){i, y, x, 0}, q[++cnt] = i;
  }
  CDQ(1, tot);
  for (int i = 1; i <= cnt; i++) printf("%d\n", ans[q[i]]);
}
