#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
struct node {
  int a, b, val, id;
} p[700100], cp[700100];
int n, m, cnt, q, a[N], pre[N];
long long c[N], ans[N];
set<int> st[N];
set<int>::iterator las, nxt;
int read() {
  int aa = 0, bb = 1;
  char cc = getchar();
  while (cc > '9' || cc < '0') {
    if (cc == '-') bb = -1;
    cc = getchar();
  }
  while (cc >= '0' && cc <= '9') {
    aa = (aa << 3) + (aa << 1) + (cc ^ '0');
    cc = getchar();
  }
  return aa * bb;
}
int lowbit(int x) { return x & (-x); }
void add(int x, int val) {
  while (x <= n) c[x] += val, x += lowbit(x);
}
long long query(int x) {
  long long as = 0;
  while (x) as += c[x], x -= lowbit(x);
  return as;
}
void cdq(int l, int r) {
  if (l == r) return;
  int mid = l + r >> 1;
  cdq(l, mid);
  cdq(mid + 1, r);
  int i = l, j = mid + 1;
  while (j <= r) {
    if (!p[j].id) {
      j++;
      continue;
    }
    while (i <= mid && p[i].a <= p[j].a) add(p[i].b, p[i].val), i++;
    ans[p[j].id] += query(n) - query(p[j].b - 1);
    j++;
  }
  i--;
  while (i >= l) add(p[i].b, -p[i].val), i--;
  i = l;
  j = mid + 1;
  int pos = l - 1;
  while (pos < r) {
    if (i > mid)
      cp[++pos] = p[j++];
    else if (j > r)
      cp[++pos] = p[i++];
    else {
      if (p[i].a <= p[j].a)
        cp[++pos] = p[i++];
      else
        cp[++pos] = p[j++];
    }
  }
  for (i = l; i <= r; i++) p[i] = cp[i];
}
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    if (pre[a[i]]) p[++cnt] = (node){i, pre[a[i]], i - pre[a[i]], 0};
    pre[a[i]] = i;
    st[a[i]].insert(i);
  }
  int opt, x, y;
  for (int i = 1; i <= m; i++) {
    opt = read();
    x = read();
    y = read();
    if (opt == 1) {
      st[a[x]].erase(x);
      if (st[a[x]].size() == 0)
        ;
      else {
        las = st[a[x]].upper_bound(x);
        if (las == st[a[x]].end()) {
          las--;
          p[++cnt] = (node){x, *las, *las - x, 0};
        } else if (las == st[a[x]].begin()) {
          nxt = las;
          p[++cnt] = (node){*nxt, x, x - *nxt, 0};
        } else {
          nxt = las--;
          p[++cnt] = (node){x, *las, *las - x, 0};
          p[++cnt] = (node){*nxt, x, x - *nxt, 0};
          p[++cnt] = (node){*nxt, *las, *nxt - *las, 0};
        }
      }
      a[x] = y;
      if (st[y].size() == 0)
        ;
      else {
        las = st[y].upper_bound(x);
        if (las == st[y].end()) {
          las--;
          p[++cnt] = (node){x, *las, x - *las, 0};
        } else if (las == st[y].begin()) {
          nxt = las;
          p[++cnt] = (node){*nxt, x, *nxt - x, 0};
        } else {
          nxt = las--;
          p[++cnt] = (node){*nxt, *las, *las - *nxt, 0};
          p[++cnt] = (node){x, *las, x - *las, 0};
          p[++cnt] = (node){*nxt, x, *nxt - x, 0};
        }
      }
      st[y].insert(x);
    } else
      p[++cnt] = (node){y, x, 0, ++q};
  }
  cdq(1, cnt);
  for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
  return 0;
}
