#include <bits/stdc++.h>
const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const long long MXLL = 9223372036854775807;
const int Sz = 2e5 + 1;
using namespace std;
inline void Read_rap() {
  ios_base ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
inline void randomizer3000() {
  unsigned int seed;
  asm("rdtsc" : "=A"(seed));
  srand(seed);
}
int n, m;
int a[Sz];
set<int> pos[Sz];
long long sum(long long x) { return x * (x + 1) / 2; }
long long sum(long long l, long long r) { return sum(r) - sum(l - 1); }
struct fenwick {
  int n;
  vector<int> t;
  fenwick(int n) : n(n), t(n + 1) {}
  void update(int id, int delta) {
    for (int i = id; i <= n; i |= (i + 1)) t[i] += delta;
  }
  long long get(int l) {
    long long res = 0;
    for (int i = l; i >= 1; i = (i & (i + 1)) - 1) res += t[i];
    return res;
  }
  long long get(int l, int r) { return get(r) - get(l - 1); }
};
struct SQRT {
  int n;
  int sz;
  vector<int> a;
  vector<fenwick> t;
  vector<int> bl;
  SQRT(int n, vector<int> &a)
      : n(n), sz(1000), a(a), t(n / sz + 1, fenwick(n)), bl(n + 1) {
    for (int i = 1; i <= n; i++) {
      bl[i] = i / sz;
      t[bl[i]].update(a[i], a[i]);
    }
  }
  void update(int id, int x) {
    t[bl[id]].update(a[id], -(id - a[id]));
    a[id] = x;
    t[bl[id]].update(a[id], (id - a[id]));
  }
  long long loop(int l, int r, int k) {
    long long sum = 0;
    for (int i = l; i <= r; i++)
      if (a[i] >= k) sum += i - a[i];
    return sum;
  }
  long long get(int l, int r) {
    long long sum = 0;
    if (bl[l] == bl[r])
      sum = loop(l, r, l);
    else {
      sum += loop(l, min(n, (bl[l] + 1) * sz - 1), l);
      sum += loop(max(1, bl[r] * sz), r, l);
      for (int i = bl[l] + 1; i <= bl[r] - 1; i++) sum += t[i].get(l, n);
    }
    return sum;
  }
};
int main() {
  scanf("%d %d", &n, &m);
  vector<int> prv(n + 1);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    if (pos[a[i]].size())
      prv[i] = *pos[a[i]].rbegin();
    else
      prv[i] = i;
    pos[a[i]].insert(i);
  }
  SQRT T(n, prv);
  while (m--) {
    int tp, x, y;
    scanf("%d %d %d", &tp, &x, &y);
    if (tp == 1) {
      if (a[x] == y) continue;
      if (x != *pos[a[x]].rbegin()) {
        int p = *upper_bound(pos[a[x]].begin(), pos[a[x]].end(), x);
        assert(prv[p] == x);
        if (prv[x] == x)
          prv[p] = p;
        else
          prv[p] = prv[x];
        T.update(p, prv[p]);
      }
      pos[a[x]].erase(x);
      a[x] = y;
      pos[y].insert(x);
      auto it = upper_bound(pos[y].begin(), pos[y].end(), x);
      if (it != pos[y].end()) {
        T.update(*it, x);
        prv[*it] = x;
      }
      it--;
      if (it != pos[y].begin()) {
        it--;
        T.update(x, *it);
        prv[x] = *it;
      } else {
        prv[x] = x;
        T.update(x, prv[x]);
      }
    } else {
      printf("%I64d\n", T.get(x, y));
    }
  }
  return 0;
}
