#include <bits/stdc++.h>
using namespace std;
template <typename _T>
inline void _DBG(const char *s, _T x) {
  cerr << s << " = " << x << "\n";
}
template <typename _T, typename... args>
void _DBG(const char *s, _T x, args... a) {
  while (*s != ',') cerr << *s++;
  cerr << " = " << x << ',';
  _DBG(s + 1, a...);
}
struct Fenwick2D {
  int MAX_X = 1e5 + 7, MAX_Y = 1e5 + 7;
  unordered_map<int, unordered_map<int, long long> > tree;
  inline void update(int x, int y, long long val) {
    for (int i = x + 1; i <= MAX_X; i += (i & -i))
      for (int j = y + 1; j <= MAX_Y; j += (j & -j)) tree[i][j] += val;
  }
  inline long long pref(int x, int y) {
    long long res = 0;
    for (int i = x; i; i -= (i & -i)) {
      if (tree.find(i) == tree.end()) continue;
      for (int j = y; j; j -= (j & -j))
        if (tree[i].find(j) != tree[i].end()) res += tree[i][j];
    }
    return res;
  }
  inline long long query(int x1, int x2, int y1, int y2) {
    x2++, y2++;
    return pref(x2, y2) - pref(x2, y1) - pref(x1, y2) + pref(x1, y1);
  }
};
const int N = 1e5 + 7;
int n, m, T[N], pre[N], g[N];
set<int> R[N], S[N];
Fenwick2D tree;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    S[i].insert(n + 1);
    R[i].insert(0);
    cin >> T[i];
    R[T[i]].insert(-i);
    S[T[i]].insert(i);
    pre[i] = g[T[i]], g[T[i]] = i;
    tree.update(i, pre[i], i - pre[i]);
  }
  while (m--) {
    int t, a, b;
    cin >> t >> a >> b;
    if (t == 1) {
      int nx = *S[T[a]].upper_bound(a);
      tree.update(a, pre[a], pre[a] - a);
      if (nx <= n) {
        tree.update(nx, pre[nx], pre[nx] - nx);
        pre[nx] = pre[a];
        tree.update(nx, pre[nx], nx - pre[nx]);
      }
      S[T[a]].erase(a);
      R[T[a]].erase(-a);
      T[a] = b;
      nx = *S[T[a]].upper_bound(a);
      pre[a] = -(*R[T[a]].upper_bound(-a));
      if (nx <= n) {
        tree.update(nx, pre[nx], pre[nx] - nx);
        pre[nx] = a;
        tree.update(nx, pre[nx], nx - pre[nx]);
      }
      S[T[a]].insert(a), R[T[a]].insert(-a);
      tree.update(a, pre[a], a - pre[a]);
    } else {
      cout << tree.query(a, b, a, b) << "\n";
    }
  }
  return 0;
}
