#include <bits/stdc++.h>
using namespace std;
struct node {
  int op, x, y, v, id;
} a[100005 * 10];
bool cmp1(node tx, node ty) { return tx.id < ty.id; }
bool cmp2(node tx, node ty) { return tx.x > ty.x; }
int n, m, p, q, o[100005];
set<int> s[100005];
long long ans[100005], c[100005];
int lowbit(int x) { return x & (-x); }
void add(int x, int k) {
  for (int i = x; i <= n; i += lowbit(i)) c[i] += k;
}
long long sum(int x) {
  long long ans = 0;
  for (int i = x; i; i -= lowbit(i)) ans += c[i];
  return ans;
}
void cdq(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  cdq(l, mid);
  sort(a + l, a + mid + 1, cmp2);
  sort(a + mid + 1, a + r + 1, cmp2);
  int h1 = l, h2 = mid + 1;
  while (h2 <= r) {
    while (h1 <= mid && a[h1].x >= a[h2].x) {
      if (!a[h1].op) add(a[h1].y, a[h1].v);
      h1++;
    }
    if (a[h2].op) ans[a[h2].v] += sum(a[h2].y);
    h2++;
  }
  for (int i = l; i < h1; i++)
    if (!a[i].op) add(a[i].y, -a[i].v);
  sort(a + l, a + r + 1, cmp1);
  cdq(mid + 1, r);
}
void upd(int x, int op) {
  int l, r;
  l = *--s[o[x]].lower_bound(x);
  r = *s[o[x]].upper_bound(x);
  ++q, a[q] = (node){0, l, x, (x - l) * op, q};
  ++q, a[q] = (node){0, l, r, (l - r) * op, q};
  ++q, a[q] = (node){0, x, r, (r - x) * op, q};
}
int main() {
  int op, x, y;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &o[i]);
    s[i].insert(0);
    s[i].insert(INT_MAX / 2);
    s[o[i]].insert(i);
  }
  for (int i = 1; i <= n; i++) {
    x = *--s[o[i]].lower_bound(i);
    ++q, a[q] = (node){0, x, i, i - x, q};
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d %d %d", &op, &x, &y);
    if (op == 1) {
      upd(x, -1), s[o[x]].erase(x);
      o[x] = y;
      upd(x, 1), s[o[x]].insert(x);
    } else
      ++q, a[q] = (node){1, x, y, ++p, q};
  }
  cdq(1, q);
  for (int i = 1; i <= p; i++) printf("%lld\n", ans[i]);
  return 0;
}
