#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct vec {
  T* a;
  int n;
  void clear() { n = 0; }
  void push_back(const T& x) {
    if ((n & -n) == n) a = (T*)realloc(a, (n * 2) * sizeof(T));
    a[n++] = x;
  }
  inline T* begin() { return a; }
  inline T* end() { return a + n; }
};
set<int> app[100066];
const int M = 131072;
int n, m, x[277777], ro[277777];
long long sum[14700000];
int ch[14700000][2], rot[277777], an = 0;
void ins(int r1, int& r2, int l, int r, int p, int q) {
  if (r1)
    r2 = r1;
  else
    r2 = ++an;
  sum[r2] = sum[r1] + q;
  if (l == r) return;
  int mid = l + r >> 1;
  if (p <= mid)
    ins(ch[r1][0], ch[r2][0], l, mid, p, q), ch[r2][1] = ch[r1][1];
  else
    ins(ch[r1][1], ch[r2][1], mid + 1, r, p, q), ch[r2][0] = ch[r1][0];
}
long long query(int ro, int l, int r, int p) {
  if (l > p || !sum[ro]) return 0;
  if (r <= p) return sum[ro];
  int mid = l + r >> 1;
  long long ans = 0;
  ans += query(ch[ro][0], l, mid, min(p, mid));
  if (p > mid) ans += query(ch[ro][1], mid + 1, r, p);
  return ans;
}
void ins(int x, int y, int z) {
  for (; y <= n; y += y & -y) ins(ro[y], ro[y], 1, n, x, z);
}
long long qry(int x, int y) {
  long long ans = 0;
  for (; y >= 1; y -= y & -y) {
    int b = ro[y];
    ans += sum[b] - query(b, 1, n, x - 1);
  }
  return ans;
}
void init(int x) {
  for (auto g = app[x].begin(); g != app[x].end(); ++g)
    if (g != app[x].begin()) {
      auto s = g;
      --s;
      ins(*s, *g, *g - *s);
    }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", x + i), app[x[i]].insert(i);
  for (int i = 1; i <= n; ++i) init(i);
  while (m--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if (a == 1) {
      auto w = app[x[b]].find(b);
      int A = 0;
      if (w != app[x[b]].begin()) {
        auto s = w;
        --s;
        ++A;
        ins(*s, *w, *s - *w);
      }
      {
        auto s = w;
        ++s;
        if (s != app[x[b]].end()) ins(*w, *s, *w - *s), ++A;
      }
      if (A == 2) {
        auto a = w, b = w;
        --a, ++b;
        ins(*a, *b, *b - *a);
      }
      A = 0;
      app[x[b]].erase(w);
      x[b] = c;
      w = app[c].insert(b).first;
      if (w != app[c].begin()) {
        auto s = w;
        --s;
        ins(*s, *w, *w - *s), ++A;
      }
      {
        auto s = w;
        ++s;
        if (s != app[c].end()) ins(*w, *s, *s - *w), ++A;
      }
      if (A == 2) {
        auto a = w, b = w;
        --a, ++b;
        ins(*a, *b, *a - *b);
      }
    } else
      printf("%I64d\n", qry(b, c));
  }
}
