#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 20;
int n, m;
struct line {
  int type, x, y, lag;
  line() { type = x = y = lag = 0; }
  line(int a, int b, int c, int d) { type = a, x = b, y = c, lag = d; }
  bool operator<(const line &a) const { return y > a.y; }
} t[7 * N];
int a[N], qu;
set<int> s[N];
long long f[N], ans[N];
void add(int x, int y) {
  while (x <= n) {
    f[x] += y;
    x += x & (-x);
  }
}
long long query(int x) {
  long long ret = 0;
  while (x) {
    ret += f[x];
    x -= x & (-x);
  }
  return ret;
}
void cdq(int l, int r) {
  if (l == r) return;
  int mid = l + r >> 1;
  cdq(l, mid), cdq(mid + 1, r);
  int j = l;
  for (int i = mid + 1; i <= r; i++) {
    while (j <= mid && t[j].y >= t[i].y) {
      if (t[j].type == 0) add(t[j].x, (t[j].x - t[j].y) * t[j].lag);
      j++;
    }
    if (t[i].type == 1) ans[t[i].lag] += query(t[i].x);
  }
  for (int i = l; i < j; i++)
    if (t[i].type == 0) add(t[i].x, -(t[i].x - t[i].y) * t[i].lag);
  sort(t + l, t + r + 1);
}
set<int>::iterator it;
int main() {
  scanf("%d%d", &n, &m);
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    if (s[a[i]].size()) {
      it = s[a[i]].end();
      it--;
      t[++cnt] = line(0, i, *it, 1);
    } else
      t[++cnt] = line(0, i, 0, 1);
    s[a[i]].insert(i);
  }
  int opt, x, y;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &opt, &x, &y);
    if (opt == 1) {
      int L = 0, R = 0;
      it = s[a[x]].find(x);
      if (it != s[a[x]].begin()) t[++cnt] = line(0, x, L = *--it, -1), it++;
      if (++it != s[a[x]].end()) t[++cnt] = line(0, R = *it, x, -1);
      if (L && R) t[++cnt] = line(0, R, L, 1);
      s[a[x]].erase(x);
      s[a[x] = y].insert(x);
      it = s[y].find(x), L = R = 0;
      if (it != s[y].begin()) t[++cnt] = line(0, x, L = *--it, 1), it++;
      if (++it != s[y].end()) t[++cnt] = line(0, R = *it, x, 1);
      if (L && R) t[++cnt] = line(0, R, L, -1);
    } else
      t[++cnt] = line(1, y, x, ++qu);
  }
  cdq(1, cnt);
  for (int i = 1; i <= qu; i++) printf("%lld\n", ans[i]);
  return 0;
}
