#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long int LINF = 0x3f3f3f3f3f3f3f3fll;
const long double pi = acos(-1);
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;
pair<int, int> limb[50];
int qntb;
long long int ps[50][50];
int id[N];
set<int> pos[N];
int v[N];
int cor[N];
int n, q;
long long int dragao(int e, int d, int x) {
  set<int>::iterator it1, it2;
  it1 = pos[x].lower_bound(e);
  if (it1 == pos[x].end()) return 0;
  it2 = pos[x].upper_bound(d);
  if (it2 == pos[x].begin()) return 0;
  --it2;
  return *it2 - *it1;
}
void upd(int p, int x, int y) {
  int l = id[p];
  for (int i = l; i >= 0; i--)
    for (int j = l; j < qntb; j++) {
      ps[i][j] -= dragao(limb[i].first, limb[j].second, x) +
                  dragao(limb[i].first, limb[j].second, y);
    }
  pos[x].erase(p);
  pos[y].insert(p);
  for (int i = l; i >= 0; i--)
    for (int j = l; j < qntb; j++) {
      ps[i][j] += dragao(limb[i].first, limb[j].second, x) +
                  dragao(limb[i].first, limb[j].second, y);
    }
  v[p] = y;
}
long long int query(int e, int d, int t) {
  int lb = -1, ub = -1;
  for (int i = 0; i < qntb; i++) {
    if (limb[i].first >= e and limb[i].second <= d) {
      if (lb == -1) lb = i;
      ub = i;
    }
  }
  if (ub == -1) {
    long long int r = 0;
    for (int i = e; i <= d; i++) {
      if (cor[v[i]] != t) {
        r += dragao(e, d, v[i]);
        cor[v[i]] = t;
      }
    }
    return r;
  }
  long long int r = ps[lb][ub];
  int E = limb[lb].first, D = limb[ub].second;
  for (int i = e; i < E; i++) {
    if (cor[v[i]] != t) {
      r += dragao(e, d, v[i]) - dragao(E, D, v[i]);
      cor[v[i]] = t;
    }
  }
  for (int i = D + 1; i <= d; i++) {
    if (cor[v[i]] != t) {
      r += dragao(e, d, v[i]) - dragao(E, D, v[i]);
      cor[v[i]] = t;
    }
  }
  return r;
}
void pre() {
  cin >> n >> q;
  int c = 0, ini = -1;
  for (int i = 1; i <= n; i++) {
    cin >> v[i];
    pos[v[i]].insert(i);
    id[i] = qntb;
    if (ini == -1) ini = i;
    c++;
    if (c == 2200) {
      c = 0;
      limb[qntb].first = ini;
      ini = -1;
      limb[qntb].second = i;
      qntb++;
    }
  }
  if (c != 0) {
    limb[qntb].first = ini;
    limb[qntb].second = n;
    qntb++;
  }
  for (int i = 1; i <= n; i++) {
    upd(i, -1, v[i]);
  }
}
int main() {
  pre();
  for (int i = 1; i <= q; i++) {
    int p, x, y;
    cin >> p >> x >> y;
    if (p == 1) {
      upd(x, v[x], y);
    } else {
      long long int r = query(x, y, i);
      cout << r << endl;
    }
  }
  return 0;
}
