#include <bits/stdc++.h>
using namespace std;
const int M = 1e5 + 4;
int a[M], b[M], n, m;
set<int> s[M];
vector<int> vec[4 * M], pqu[M];
long long* fen[4 * M];
int typ[M], lq[M], rq[M];
void build(int l = 1, int r = n, int id = 1) {
  if (r - l < 2) {
    vec[id] = pqu[l];
    sort(vec[id].begin(), vec[id].end());
    vec[id].resize(unique(vec[id].begin(), vec[id].end()) - vec[id].begin());
    fen[id] = new long long[(const int)(vec[id].size() + 1)];
    return;
  }
  int mid = (l + r) / 2;
  build(l, mid, 2 * id), build(mid, r, 2 * id + 1);
  vec[id].resize(vec[2 * id].size() + vec[2 * id + 1].size());
  merge(vec[2 * id].begin(), vec[2 * id].end(), vec[2 * id + 1].begin(),
        vec[2 * id + 1].end(), vec[id].begin());
  vec[id].resize(unique(vec[id].begin(), vec[id].end()) - vec[id].begin());
  fen[id] = new long long[(const int)(vec[id].size() + 1)];
}
void add_fen(int p, int id, int val) {
  for (; p <= vec[id].size(); p += p & -p) fen[id][p] += val;
}
long long get_fen(int p, int id) {
  long long ret = 0;
  for (; p; p -= p & -p) ret += fen[id][p];
  return ret;
}
long long get(int ql, int qr, int l = 1, int r = n, int id = 1) {
  if (r <= ql || qr <= l) return 0;
  if (ql <= l && r <= qr) {
    int p = lower_bound(vec[id].begin(), vec[id].end(), ql) - vec[id].begin();
    return get_fen(vec[id].size(), id) - get_fen(p, id);
  }
  int mid = (l + r) / 2;
  return get(ql, qr, l, mid, 2 * id) + get(ql, qr, mid, r, 2 * id + 1);
}
void add(int p, int ql, int val, int l = 1, int r = n, int id = 1) {
  int pos =
      lower_bound(vec[id].begin(), vec[id].end(), ql) - vec[id].begin() + 1;
  add_fen(pos, id, val);
  if (r - l < 2) return;
  int mid = (l + r) / 2;
  if (p < mid)
    add(p, ql, val, l, mid, 2 * id);
  else
    add(p, ql, val, mid, r, 2 * id + 1);
}
void upd_baze_seg(int lo, int p, int ri, int nes) {
  if (ri) add(ri, p, (ri - p) * nes);
  if (lo) add(p, lo, (p - lo) * nes);
  if (ri && lo) add(ri, lo, (ri - lo) * (-nes));
}
void upd_baze_baze(int lo, int p, int ri) {
  if (ri) pqu[ri].push_back(p);
  if (lo) pqu[p].push_back(lo);
  if (ri && lo) pqu[ri].push_back(lo);
}
void upd_baze(int p, int val, int nes, bool f) {
  auto it_jolo = s[val].upper_bound(p);
  auto it_back = s[val].lower_bound(p);
  int ri = 0, lo = 0;
  if (it_jolo != s[val].end()) ri = *it_jolo;
  if (s[val].size() && it_back != s[val].begin()) --it_back, lo = *it_back;
  if (!f)
    upd_baze_baze(lo, p, ri);
  else
    upd_baze_seg(lo, p, ri, nes);
  if (nes == -1)
    s[val].erase(p);
  else
    s[val].insert(p);
}
void pre() {
  cin >> n >> m, n++;
  for (int i = 1; i < n; i++) {
    scanf("%d", a + i), b[i] = a[i];
    upd_baze(i, a[i], 1, 0);
  }
  for (int j = 0; j < m; j++) {
    scanf("%d%d%d", typ + j, lq + j, rq + j);
    if (typ[j] == 1) {
      int p = lq[j], x = rq[j];
      if (x == a[p]) continue;
      upd_baze(p, a[p], -1, 0);
      upd_baze(p, x, 1, 0);
      a[p] = x;
    }
  }
  build();
  for (int i = 0; i < M; i++) s[i].clear(), a[i] = b[i];
}
int32_t main() {
  pre();
  for (int i = 1; i < n; i++) upd_baze(i, a[i], 1, 1);
  for (int j = 0; j < m; j++) {
    if (typ[j] == 1) {
      int p = lq[j], x = rq[j];
      if (x == a[p]) continue;
      upd_baze(p, a[p], -1, 1);
      upd_baze(p, x, 1, 1);
      a[p] = x;
    } else
      printf("%lld\n", get(lq[j], rq[j] + 1));
  }
  return 0;
}
