#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
set<int> col[N];
int n, m, val[N], a[N];
struct cd {
  int op, p, pr, val, id;
} q[N * 10], p[N * 10];
int pre[N], tot;
long long c[N], ans[N];
void add(int x, long long val) {
  while (x) {
    c[x] += val;
    x -= x & -x;
  }
}
long long query(int x) {
  long long ret = 0;
  while (x <= n) {
    ret += c[x];
    x += x & -x;
  }
  return ret;
}
void clear(int x) {
  while (x) {
    c[x] = 0;
    x -= x & -x;
  }
}
bool cmp(cd a, cd b) { return a.p < b.p; }
void cdq(int L, int R) {
  if (L == R) return;
  int M = L + R >> 1;
  cdq(L, M);
  cdq(M + 1, R);
  int j = L, c = L;
  for (int i = M + 1; i <= R; i++) {
    while (j <= M && q[j].p <= q[i].p) {
      if (q[j].op == 1) add(q[j].pr, q[j].val);
      p[c++] = q[j++];
    }
    if (q[i].op == 2) ans[q[i].id] += query(q[i].pr);
    p[c++] = q[i];
  }
  for (int i = L; i < j; i++)
    if (q[i].op == 1) clear(q[i].pr);
  for (int i = j; i <= M; i++) p[c++] = q[i];
  for (int i = L; i < c; i++) q[i] = p[i];
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    if (col[a[i]].empty())
      pre[i] = 0;
    else
      pre[i] = *--col[a[i]].end();
    col[a[i]].insert(i);
    q[++tot] = (cd){1, i, pre[i], i - pre[i], 0};
  }
  for (int i = 1; i <= n; i++) col[i].insert(0);
  int qt = 0;
  for (int i = 1; i <= m; i++) {
    int op, x, y, nex;
    scanf("%d%d%d", &op, &x, &y);
    if (op == 1) {
      q[++tot] = (cd){op, x, pre[x], pre[x] - x, 0};
      if (++col[a[x]].lower_bound(x) != col[a[x]].end()) {
        nex = *++col[a[x]].lower_bound(x);
        q[++tot] = (cd){op, nex, pre[nex], pre[nex] - nex, 0};
        pre[nex] = pre[x];
        q[++tot] = (cd){op, nex, pre[nex], nex - pre[nex], 0};
      }
      col[a[x]].erase(x);
      a[x] = y;
      col[a[x]].insert(x);
      pre[x] = *--col[a[x]].lower_bound(x);
      q[++tot] = (cd){op, x, pre[x], x - pre[x], 0};
      if (++col[a[x]].lower_bound(x) != col[a[x]].end()) {
        nex = *++col[a[x]].lower_bound(x);
        q[++tot] = (cd){op, nex, pre[nex], pre[nex] - nex, 0};
        pre[nex] = x;
        q[++tot] = (cd){op, nex, pre[nex], nex - pre[nex], 0};
      }
    } else {
      q[++tot] = (cd){op, y, x, 0, ++qt};
    }
  }
  cdq(1, tot);
  for (int i = 1; i <= qt; i++) printf("%lld\n", ans[i]);
  return 0;
}
