#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15;
set<int> st[N];
int l, r, x, p, n, m, t, A[N];
struct fen {
  unordered_map<int, long long> mp[N];
  fen() {
    for (int i = 1; i <= N - 1; i++) mp[i].max_load_factor(0.15);
  }
  void add(int l, int R, int d) {
    for (l++; l < N; l += l & (-l))
      for (int r = R + 1; r < N; r += r & (-r)) {
        mp[l][r] += d;
        if (!mp[l][r]) mp[l].erase(r);
      }
  }
  long long get(int l, int R) {
    long long sm = 0;
    for (l++; l > 0; l -= l & (-l))
      for (int r = R + 1; r > 0; r -= r & (-r))
        sm += mp[l].count(r) ? mp[l][r] : 0;
    return (sm);
  }
  long long g(int l, int r) { return (get(N - 5, r) - get(l - 1, r)); }
};
int main() {
  fen f;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", A + i), st[A[i]].insert(i);
  for (int i = 1; i <= n; i++)
    if ((int)st[i].size() > 1) {
      auto it = st[i].begin();
      auto it2 = it;
      it2++;
      for (int j = 1; j < (int)st[i].size(); j++) {
        f.add(*it, *it2, *it2 - *it);
        it++, it2++;
      }
    }
  for (int i = 1; i <= m; i++) {
    scanf("%d", &t);
    if (t & 1) {
      scanf("%d %d", &p, &x);
      auto it = st[A[p]].find(p);
      if (it != st[A[p]].begin()) {
        auto it2 = st[A[p]].find(p);
        it2--;
        f.add(*it2, *it, *it2 - *it);
      }
      if (*it != *st[A[p]].rbegin()) {
        auto it2 = st[A[p]].find(p);
        it2++;
        f.add(*it, *it2, *it - *it2);
      }
      st[A[p]].erase(p);
      A[p] = x;
      st[x].insert(p);
      it = st[x].find(p);
      if (it != st[x].begin()) {
        auto it2 = st[x].find(p);
        it2--;
        f.add(*it2, *it, *it - *it2);
      }
      if (*it != *st[x].rbegin()) {
        auto it2 = st[x].find(p);
        it2++;
        f.add(*it, *it2, *it2 - *it);
      }
      it = st[x].find(p);
      if (it != st[x].begin() && *it != *st[x].rbegin()) {
        auto it2 = it, it3 = it;
        it2--, it3++;
        f.add(*it2, *it3, *it2 - *it3);
      }
      continue;
    }
    scanf("%d %d", &l, &r);
    printf("%I64d\n", f.g(l, r));
  }
}
