#include <bits/stdc++.h>
using namespace std;
bool Handsome;
inline void Mi(int &x, int y) {
  if (x > y && (x = y))
    ;
}
inline void Mx(int &x, int y) {
  if (x < y && (x = y))
    ;
}
const int M = 1e6 + 5;
int n, m, a[M], cnt, q;
long long ans[M];
struct node {
  int l, r, z, id;
} A[M], B[M];
set<int> s[M];
set<int>::iterator it;
struct BIT {
  long long t[M];
  void add(int x, long long y) {
    for (; x; x -= x & -x) t[x] += y;
  }
  long long ask(int x) {
    long long res = 0;
    for (; x <= n; x += x & -x) res += t[x];
    return res;
  }
} bit;
void CDQ(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1, p = l;
  CDQ(l, mid);
  CDQ(mid + 1, r);
  for (int i = mid + 1, iend = r; i <= iend; ++i) {
    while (p <= mid && A[p].r <= A[i].r) {
      if (!A[p].id) bit.add(A[p].l, A[p].z);
      ++p;
    }
    if (A[i].id) ans[A[i].id] += bit.ask(A[i].l);
  }
  while (p > l) {
    --p;
    if (!A[p].id) bit.add(A[p].l, -A[p].z);
  }
  int t = l;
  for (int i = l, iend = r; i <= iend; ++i) B[i] = A[i];
  for (int i = mid + 1, iend = r; i <= iend; ++i) {
    while (p <= mid && B[p].r <= B[i].r) A[t++] = B[p++];
    A[t++] = B[i];
  }
  while (p <= mid) A[t++] = B[p++];
}
bool Most;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1, iend = n; i <= iend; ++i) scanf("%d", &a[i]);
  for (int i = 1, iend = n; i <= iend; ++i) s[a[i]].insert(i);
  for (int i = 1, iend = n; i <= iend; ++i) {
    int l = 0;
    for (it = s[i].begin(); it != s[i].end(); l = *it, ++it)
      if (l) A[++cnt] = (node){l, *it, *it - l, 0};
  }
  for (int i = 1, iend = m; i <= iend; ++i) {
    int op, x, y;
    scanf("%d%d%d", &op, &x, &y);
    if (op == 1) {
      int l = 0, r = 0;
      it = s[a[x]].lower_bound(x);
      if (it != s[a[x]].begin()) --it, l = *it, ++it;
      ++it;
      if (it != s[a[x]].end()) r = *it;
      --it;
      s[a[x]].erase(it);
      if (l) A[++cnt] = (node){l, x, l - x, 0};
      if (r) A[++cnt] = (node){x, r, x - r, 0};
      if (l && r) A[++cnt] = (node){l, r, r - l, 0};
      l = r = 0;
      it = s[a[x] = y].lower_bound(x);
      if (it != s[y].begin()) --it, l = *it, ++it;
      if (it != s[a[x]].end()) r = *it;
      s[y].insert(x);
      if (l) A[++cnt] = (node){l, x, x - l, 0};
      if (r) A[++cnt] = (node){x, r, r - x, 0};
      if (l && r) A[++cnt] = (node){l, r, l - r, 0};
    }
    if (op == 2) A[++cnt] = (node){x, y, 0, ++q};
  }
  CDQ(1, cnt);
  for (int i = 1, iend = q; i <= iend; ++i) printf("%lld\n", ans[i]);
  return 0;
}
