#include <bits/stdc++.h>
using namespace std;
template <typename T>
T gcd(T x, T y) {
  if (x < y) swap(x, y);
  while (y > 0) {
    T f = x % y;
    x = y;
    y = f;
  }
  return x;
}
const int maxn = 100007;
int BLOCKSIZE = 500;
set<int> s[maxn];
int a[maxn];
int nxt[maxn];
int prv[maxn];
int n, m;
long long b[maxn];
int d[maxn];
int lst[maxn];
long long query(int block, int R) {
  int iBlockStart = block * BLOCKSIZE;
  int iBlockEnd = min((block + 1) * BLOCKSIZE, n);
  int idx = upper_bound(d + iBlockStart, d + iBlockEnd, R,
                        [](int i, int j) { return i < nxt[j]; }) -
            d;
  if (idx == iBlockStart) return 0;
  return b[idx - 1];
}
void updateBlock(int block) {
  int iBlockStart = block * BLOCKSIZE;
  int iBlockEnd = min((block + 1) * BLOCKSIZE, n);
  sort(d + iBlockStart, d + iBlockEnd,
       [](int i, int j) { return nxt[i] < nxt[j]; });
  b[iBlockStart] = nxt[d[iBlockStart]] - d[iBlockStart];
  for (int i = iBlockStart + 1; i < iBlockEnd; i++)
    b[i] = b[i - 1] + nxt[d[i]] - d[i];
}
int main(int argc, char *argv[]) {
  std::cin.sync_with_stdio(false);
  std::cin.tie(nullptr);
  cin >> n >> m;
  {
    for (int i = 0; i < n; i++) nxt[i] = n, prv[i] = -1, d[i] = i;
    memset(lst, -1, sizeof(lst));
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      int pr = lst[a[i]];
      if (pr != -1) {
        nxt[pr] = i;
        prv[i] = pr;
      }
      lst[a[i]] = i;
      s[a[i]].insert(i);
    }
    for (int i = 0; i * BLOCKSIZE < n; i++) updateBlock(i);
    for (int i = 0; i < m; i++) {
      int op;
      cin >> op;
      if (op == 1) {
        int p, x;
        cin >> p >> x;
        p--;
        if (a[p] == x) continue;
        if (nxt[p] != n) prv[nxt[p]] = prv[p];
        if (prv[p] != -1) {
          nxt[prv[p]] = nxt[p];
          if (prv[p] / BLOCKSIZE != p / BLOCKSIZE)
            updateBlock(prv[p] / BLOCKSIZE);
        }
        s[a[p]].erase(p);
        a[p] = x;
        nxt[p] = n;
        prv[p] = -1;
        auto it = s[x].emplace(p).first;
        bool updatedNext = false;
        if (it != s[x].begin()) {
          int pr = *prev(it);
          int nx = nxt[pr];
          nxt[pr] = p;
          prv[p] = pr;
          if (pr / BLOCKSIZE != p / BLOCKSIZE) updateBlock(pr / BLOCKSIZE);
          if (nx != n) {
            prv[nx] = p;
            nxt[p] = nx;
            updatedNext = true;
          }
        }
        if (!updatedNext) {
          auto nxiter = next(it);
          if (nxiter != s[x].end()) {
            int nx = *nxiter;
            prv[nx] = p;
            nxt[p] = nx;
          }
        }
        updateBlock(p / BLOCKSIZE);
      } else {
        int l, r, R;
        cin >> l >> r;
        l--;
        r--;
        R = r;
        long long res = 0;
        for (; l <= r && l % BLOCKSIZE; l++)
          if (nxt[l] <= R) res += nxt[l] - l;
        for (; l <= r && (r + 1) % BLOCKSIZE; r--)
          if (nxt[r] <= R) res += nxt[r] - r;
        if (l <= r) {
          for (int i = l / BLOCKSIZE, j = r / BLOCKSIZE; i <= j; i++) {
            res += query(i, R);
          }
        }
        cout << res << endl;
      }
    }
  }
  return 0;
}
