#include <bits/stdc++.h>
using namespace std;
long long ft[100005 + 1];
void upd(int i0, int v) {
  for (int i = i0 + 1; i <= 100005; i += i & -i) ft[i] += v;
}
long long get(int i0) {
  long long r = 0;
  for (int i = i0; i; i -= i & -i) r += ft[i];
  return r;
}
long long get(int i0, int i1) { return get(i1) - get(i0); }
int x[100005];
int n, m;
set<int> w[100005];
int z[100005];
int t[100005], aa[100005], bb[100005];
long long r[100005];
vector<pair<int, int> > q[100005];
vector<pair<int, int> > u;
int doit(int v, int a, int b) {
  auto it = w[v].lower_bound(a);
  if (it == w[v].end() || *it >= b) return 0;
  int r = *it;
  it = w[v].lower_bound(b);
  --it;
  return *it - r;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0, ThxDem = n; i < ThxDem; ++i)
    scanf("%d", x + i), x[i]--, w[x[i]].insert(i);
  for (int i = 0, ThxDem = m; i < ThxDem; ++i) {
    scanf("%d%d%d", t + i, aa + i, bb + i);
    aa[i]--;
    if (t[i] == 1) bb[i]--;
  }
  for (int k = 0; k < m; k += 250) {
    for (int i = 0, ThxDem = n; i < ThxDem; ++i) q[i].clear();
    memset(z, -1, sizeof(z));
    for (int i = k, ThxDem = min(k + 250, m); i < ThxDem; ++i)
      if (t[i] == 2) q[aa[i]].push_back(make_pair(bb[i], i));
    memset(ft, 0, sizeof(ft));
    for (int i = n - 1; i >= 0; --i) {
      if (z[x[i]] >= 0) upd(z[x[i]], z[x[i]] - i);
      z[x[i]] = i;
      for (auto p : q[i]) r[p.second] = get(i, p.first);
    }
    for (auto p : u) {
      w[x[p.first]].erase(p.first);
      x[p.first] = p.second;
      w[x[p.first]].insert(p.first);
    }
    u.clear();
    for (int i = k, ThxDem = min(k + 250, m); i < ThxDem; ++i) {
      if (t[i] == 1)
        u.push_back(make_pair(aa[i], bb[i]));
      else {
        int a = aa[i], b = bb[i];
        vector<pair<int, int> > rb;
        set<int> asd;
        for (auto p : u) {
          int k = p.first, v = p.second;
          if (k < a || k >= b) continue;
          if (!asd.count(x[k])) {
            r[i] -= doit(x[k], a, b);
            asd.insert(x[k]);
          }
          if (!asd.count(v)) {
            r[i] -= doit(v, a, b);
            asd.insert(v);
          }
        }
        for (auto p : u) {
          int k = p.first, v = p.second;
          rb.push_back(make_pair(k, x[k]));
          w[x[k]].erase(k);
          x[k] = v;
          w[x[k]].insert(k);
        }
        for (int v : asd) r[i] += doit(v, a, b);
        reverse(rb.begin(), rb.end());
        for (auto p : rb) {
          int k = p.first, v = p.second;
          w[x[k]].erase(k);
          x[k] = v;
          w[x[k]].insert(k);
        }
      }
    }
  }
  for (int i = 0, ThxDem = m; i < ThxDem; ++i)
    if (t[i] == 2) printf("%lld\n", r[i]);
  return 0;
}
