#include <bits/stdc++.h>
using namespace std;
const int M = 100005;
int read() {
  int x = 0, flag = 1;
  char c;
  while ((c = getchar()) < '0' || c > '9')
    if (c == '-') flag = -1;
  while (c >= '0' && c <= '9')
    x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  return x * flag;
}
int n, m, k, up, a[M], b[M], pre[M];
long long ans[M], bit[M];
set<int> s[M];
set<int>::iterator it;
struct node {
  int x, y, op, v;
  bool operator<(const node &b) const { return x < b.x; }
} p[7 * M];
int lowbit(int x) { return x & (-x); }
void ins(int x, int v) {
  for (; x <= up + 1; x += lowbit(x)) bit[x] += v;
}
long long ask(int x) {
  long long r = 0;
  for (; x >= 1; x -= lowbit(x)) r += bit[x];
  return r;
}
void cdq(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1, i = l;
  cdq(l, mid);
  cdq(mid + 1, r);
  sort(p + l, p + mid + 1);
  sort(p + mid + 1, p + r + 1);
  for (int j = mid + 1; j <= r; j++) {
    while (i <= mid && p[i].x <= p[j].x) {
      if (p[i].op == 1) ins(p[i].y, p[i].v);
      i++;
    }
    if (p[j].op == 2) {
      if (p[j].v > 0)
        ans[p[j].v] += ask(p[j].y);
      else
        ans[-p[j].v] -= ask(p[j].y);
    }
  }
  for (i--; i >= l; i--)
    if (p[i].op == 1) ins(p[i].y, -p[i].v);
}
int main() {
  up = n = read();
  m = read();
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    pre[i] = b[a[i]];
    b[a[i]] = i;
    s[a[i]].insert(i);
    p[i] = node{i, pre[i], 1, i - pre[i]};
  }
  for (int i = 1; i <= m; i++) {
    int op = read(), x = read(), y = read();
    if (op == 1) {
      int p1 = 0, n1 = 0, p2 = 0, n2 = 0;
      it = s[a[x]].lower_bound(x);
      if (it != s[a[x]].begin()) it--, p1 = *it, it++;
      if ((++it) != s[a[x]].end()) n1 = *it;
      it--;
      s[a[x]].erase(it);
      p[++n] = node{x, pre[x], 1, pre[x] - x};
      if (n1) {
        p[++n] = node{n1, pre[n1], 1, pre[n1] - n1};
        pre[n1] = p1;
        p[++n] = node{n1, pre[n1], 1, n1 - pre[n1]};
      }
      a[x] = y;
      s[a[x]].insert(x);
      it = s[a[x]].lower_bound(x);
      if (it != s[a[x]].begin()) it--, p2 = *it, it++;
      if ((++it) != s[a[x]].end()) n2 = *it;
      it--;
      pre[x] = p2;
      p[++n] = node{x, pre[x], 1, x - pre[x]};
      if (n2) {
        p[++n] = node{n2, pre[n2], 1, pre[n2] - n2};
        pre[n2] = x;
        p[++n] = node{n2, pre[n2], 1, n2 - pre[n2]};
      }
    } else {
      ++k;
      p[++n] = node{x - 1, x - 1, 2, k};
      p[++n] = node{y, y, 2, k};
      p[++n] = node{x - 1, y, 2, -k};
      p[++n] = node{y, x - 1, 2, -k};
    }
  }
  for (int i = 1; i <= n; i++) p[i].x++, p[i].y++;
  cdq(1, n);
  for (int i = 1; i <= k; i++) printf("%lld\n", ans[i]);
}
