#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 5, SZ = 320, INF = 1e9;
int n, m, sz, r, e[MAX], nxt[MAX], ant[MAX], last[MAX];
vector<pair<int, int> > Bnxt[SZ + 5], Bant[SZ + 5];
vector<long long> Snxt[SZ + 5], Sant[SZ + 5];
set<int> s[MAX];
void recalc(int i) {
  sort(Bant[i].begin(), Bant[i].end());
  sort(Bnxt[i].begin(), Bnxt[i].end());
  Sant[i].clear();
  Snxt[i].clear();
  Sant[i].assign(Bant[i].size(), 0);
  for (int k = 0; k < (int)Bant[i].size(); k++) {
    int prv = k == 0 ? 0 : Sant[i][k - 1];
    prv += Bant[i][k].second;
    Sant[i][k] = prv;
  }
  Snxt[i].assign(Bnxt[i].size(), 0);
  for (int k = 0; k < (int)Bnxt[i].size(); k++) {
    int prv = k == 0 ? 0 : Snxt[i][k - 1];
    prv += Bnxt[i][k].second;
    Snxt[i][k] = prv;
  }
}
vector<int> v;
void change(int a, int b) {
  if (ant[a] != -1) {
    nxt[ant[a]] = nxt[a];
    v.push_back(ant[a]);
  }
  if (nxt[a] != n) {
    ant[nxt[a]] = ant[a];
    v.push_back(nxt[a]);
  }
  v.push_back(a);
  s[b].insert(a);
  auto it = s[b].upper_bound(a);
  if (it == s[b].end())
    nxt[a] = n;
  else
    nxt[a] = *it;
  it = s[b].lower_bound(a);
  if (it == s[b].begin())
    ant[a] = -1;
  else {
    it--;
    ant[a] = *it;
  }
  if (ant[a] != -1) {
    nxt[ant[a]] = a;
    v.push_back(ant[a]);
  }
  if (nxt[a] != n) {
    ant[nxt[a]] = a;
    v.push_back(nxt[a]);
  }
  if (s[e[a]].find(a) != s[e[a]].end()) s[e[a]].erase(s[e[a]].find(a));
  e[a] = b;
}
void upd(int a, int b) {
  a--;
  if (b == e[a]) return;
  change(a, b);
  for (int pos : v) {
    int q = pos / r;
    for (auto &o : Bant[q]) o.first = ant[o.second];
    for (auto &o : Bnxt[q]) o.first = nxt[o.second];
    recalc(q);
  }
  v.clear();
}
long long query(int a, int b) {
  a--, b--;
  int q = a / r, w = b / r;
  long long sum_nxt = 0, sum_ant = 0;
  for (auto &o : Bnxt[q])
    if (o.second >= a && o.second <= b && o.first > b) sum_nxt += o.second;
  for (auto &o : Bant[q])
    if (o.second >= a && o.second <= b && o.first < a) sum_ant += o.second;
  if (q == w) return sum_nxt - sum_ant;
  for (auto &o : Bnxt[w])
    if (o.second >= a && o.second <= b && o.first > b) sum_nxt += o.second;
  for (auto &o : Bant[w])
    if (o.second >= a && o.second <= b && o.first < a) sum_ant += o.second;
  for (int i = q + 1; i < w; i++) {
    int p = upper_bound(Bnxt[i].begin(), Bnxt[i].end(), make_pair(b, INF)) -
            Bnxt[i].begin();
    long long v = Snxt[i].back();
    if (p > 0) v -= Snxt[i][p - 1];
    sum_nxt += v;
    p = lower_bound(Bant[i].begin(), Bant[i].end(), make_pair(a, -INF)) -
        Bant[i].begin() - 1;
    v = 0;
    if (p >= 0) v = Sant[i][p];
    sum_ant += v;
  }
  return sum_nxt - sum_ant;
}
int main() {
  scanf("%d%d", &n, &m);
  r = sqrt(n);
  sz = n / r + (n % r > 0);
  for (int i = 0; i <= n; i++) last[i] = -1;
  for (int i = 0; i < n; i++) {
    scanf("%d", &e[i]);
    ant[i] = last[e[i]];
    last[e[i]] = i;
    s[e[i]].insert(i);
  }
  for (int i = 0; i <= n; i++) last[i] = n;
  for (int i = n - 1; i >= 0; i--) {
    nxt[i] = last[e[i]];
    last[e[i]] = i;
  }
  for (int i = 0; i < n; i++) {
    int id = i / r;
    Bant[id].push_back({ant[i], i});
    Bnxt[id].push_back({nxt[i], i});
  }
  for (int i = 0; i < sz; i++) recalc(i);
  while (m--) {
    int op, a, b;
    scanf("%d%d%d", &op, &a, &b);
    if (op == 1)
      upd(a, b);
    else
      printf("%lld\n", query(a, b));
  }
  return 0;
}
