#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  char ch = getchar();
  long long s = 0, w = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * w;
}
long long n, m, c[300010];
set<long long> s[300010];
set<long long>::iterator it, it1, it2;
struct Node1 {
  long long c[300010];
  inline void add(long long x, long long v) {
    for (; x <= n; x += x & (-x)) c[x] += v;
  }
  inline long long que(long long x) {
    long long s = 0;
    for (; x; x -= x & (-x)) s += c[x];
    return s;
  }
  inline long long QUERY(long long L, long long R) {
    return que(R) - que(L - 1);
  }
} A;
struct Node2 {
  long long root[300010], tot;
  long long sum[300010 << 5], ls[300010 << 5], rs[300010 << 5];
  Node2() { tot = 0; }
  inline void add(long long &x, long long l, long long r, long long pos,
                  long long val) {
    if (!x) x = ++tot;
    sum[x] += val;
    if (l == r) return;
    if (pos <= ((l + r) >> 1))
      add(ls[x], l, ((l + r) >> 1), pos, val);
    else
      add(rs[x], ((l + r) >> 1) + 1, r, pos, val);
  }
  inline long long query(long long x, long long l, long long r, long long left,
                         long long right) {
    if (l == left && right == r) return sum[x];
    if (!x) return 0;
    if (right <= ((l + r) >> 1))
      return query(ls[x], l, ((l + r) >> 1), left, right);
    else if (left > ((l + r) >> 1))
      return query(rs[x], ((l + r) >> 1) + 1, r, left, right);
    else
      return query(ls[x], l, ((l + r) >> 1), left, ((l + r) >> 1)) +
             query(rs[x], ((l + r) >> 1) + 1, r, ((l + r) >> 1) + 1, right);
  }
  inline long long QUERY(long long L, long long R) {
    long long ans = 0;
    for (register long long x = R; x; x -= x & (-x))
      ans += query(root[x], 0, n, 0, L - 1);
    for (register long long x = L - 1; x; x -= x & (-x))
      ans -= query(root[x], 0, n, 0, L - 1);
    return ans;
  }
  inline void ADD(long long x, long long t, long long tag) {
    long long p = x;
    for (; x <= n; x += x & (-x)) add(root[x], 0, n, t, tag * (p - t));
  }
} B;
int main() {
  n = read(), m = read();
  for (register long long i = 1; i <= n; i++) s[i].insert(0);
  for (register long long i = 1; i <= n; i++) {
    c[i] = read();
    s[c[i]].insert(i);
  }
  for (register long long i = 1; i <= n; i++) {
    it = s[c[i]].lower_bound(i);
    it--;
    long long x = (*it);
    B.ADD(i, x, 1);
    A.add(i, i - x);
  }
  while (m--) {
    long long opt = read(), x = read(), y = read();
    if (opt == 1) {
      long long t = c[x];
      it1 = s[t].upper_bound(x), it2 = --s[t].lower_bound(x);
      if (it1 != s[t].end()) {
        A.add((*it1), x - (*it2));
        B.ADD((*it1), x, -1);
        B.ADD((*it1), (*it2), 1);
      }
      A.add(x, (*it2));
      B.ADD(x, (*it2), -1);
      s[t].erase(x);
      c[x] = y;
      t = c[x];
      s[t].insert(x);
      it1 = s[t].upper_bound(x), it2 = --s[t].lower_bound(x);
      if (it1 != s[t].end()) {
        A.add((*it1), (*it2) - x);
        B.ADD((*it1), x, 1);
        B.ADD((*it1), (*it2), -1);
      }
      A.add(x, -(*it2));
      B.ADD(x, (*it2), 1);
    }
    if (opt == 2) {
      printf("%I64d\n", A.QUERY(x, y) - B.QUERY(x, y));
    }
  }
  return 0;
}
