#include <bits/stdc++.h>
using namespace std;
template <class T>
struct cmp_2d_bit {
  int N, M;
  vector<unordered_map<int, T>> b;
  void init(int n, int m) {
    N = n + 1, M = m + 1;
    b.resize(N, {{0, 0}});
  }
  cmp_2d_bit() {}
  cmp_2d_bit(int n, int m) { init(n, m); }
  inline void update(int x, int y, T v) {
    for (++x; x < N; x += x & -x)
      for (int z = y + 1; z < M; z += z & -z) b[x][z] += v;
  }
  inline T prefix(int x, int y) {
    T a = 0;
    for (++x; x; x ^= x & -x)
      for (int z = y + 1; z; z ^= z & -z) a += b[x][z];
    return a;
  }
  inline T query(int x1, int y1, int x2, int y2) {
    return prefix(x2, y2) - prefix(x1 - 1, y2) - prefix(x2, y1 - 1) +
           prefix(x1 - 1, y1 - 1);
  }
};
const int N = 1e5 + 5;
int pr[N] = {}, nxt[N], A[N];
set<int> all[N];
cmp_2d_bit<long long> B;
const int INF = 1 << 20;
inline void go(int p, int a) {
  if (nxt[p] == INF) return;
  B.update(p, nxt[p], a * (nxt[p] - p));
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  fill(nxt + 1, nxt + n + 1, INF);
  B.init(n + 1, n + 1);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", A + i);
    all[A[i]].insert(i);
    nxt[pr[A[i]]] = i;
    pr[A[i]] = i;
  }
  for (int i = 1; i <= n; ++i) go(i, 1);
  B.init(n + 1, n + 1);
  while (m--) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int p, x;
      scanf("%d%d", &p, &x);
      go(p, -1);
      auto a = all[A[p]].find(p);
      if (a-- != all[A[p]].begin()) {
        go(*a, -1);
        nxt[*a] = nxt[p];
        go(*a, 1);
      }
      A[p] = x;
      a = all[x].insert(p).first;
      if (a != all[x].begin()) {
        --a;
        go(*a, -1);
        nxt[*a] = p;
        go(*a, 1);
        ++a;
      }
      if (++a != all[x].end()) {
        nxt[p] = *a;
      } else
        nxt[p] = INF;
      go(p, 1);
    } else {
      int l, r;
      scanf("%d%d", &l, &r);
      printf("%I64d\n", B.query(l, l, r, r));
    }
  }
}
