#include <bits/stdc++.h>
#pragma comment(linker, "/stack:20000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")
using namespace std;
const int N = 1e5 + 7, inf = 1e9 + 7, mod = 1e9 + 7;
const long long linf = (long long)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1},
          dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
const int block = 318;
int get_int() {
  char x = getchar();
  bool mns = 0;
  while (!isdigit(x)) mns |= x == '-', x = getchar();
  int res = 0;
  while (isdigit(x)) res = res * 10 + x - '0', x = getchar();
  if (mns) res = -res;
  return res;
}
void add(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
  if (x < 0) x += mod;
}
int mult(int x, int y) { return x * 1ll * y % mod; }
int sum(int x, int y) {
  add(x, y);
  return x;
}
int n, m;
int a[N], save[N];
int cur_id[N], idb[N];
long long ans[N];
int pr[N], nx[N], bfr[N];
int type[N], l[N], r[N];
struct fenwick {
  long long first[N + 1];
  void upd(int p, int x) {
    for (; p <= N; p |= p + 1) first[p] += x;
  }
  long long pref(int p) {
    long long res = 0;
    for (; p >= 0; p = (p & (p + 1)) - 1) res += first[p];
    return res;
  }
  long long get(int l, int r) {
    if (!l) return pref(r);
    return pref(r) - pref(l - 1);
  }
  void clear() { memset(first, 0, sizeof(first)); }
};
struct Super {
  int sz;
  pair<int, int> second[320];
  fenwick t;
  int ins(int x, int id) {
    second[++sz] = {x, id};
    t.upd(x, id);
    return sz;
  }
  int size() { return sz; }
  bool check(int id, int l, int r, int x, int y) {
    return l <= second[id].second && second[id].second <= r &&
           x <= second[id].first && second[id].first <= y;
  }
  void upd(int p, int x) {
    t.upd(second[p].first, -second[p].second);
    second[p].first = x;
    t.upd(second[p].first, second[p].second);
  }
  void clear() {
    sz = 0;
    t.clear();
  }
} t[320];
long long get(int l, int r, int x, int y) {
  int sb = idb[l], ob = idb[r];
  long long res = 0;
  if (sb == ob) {
    for (int i = cur_id[l]; i <= cur_id[r]; i++) {
      if (t[sb].check(i, l, r, x, y)) res += t[sb].second[i].second;
    }
  } else {
    for (int i = cur_id[l]; i <= (int)t[sb].size(); i++) {
      if (t[sb].check(i, l, r, x, y)) res += t[sb].second[i].second;
    }
    for (int i = sb + 1; i <= ob - 1; i++) {
      res += t[i].t.get(x, y);
    }
    for (int i = 1; i <= cur_id[r]; i++) {
      if (t[ob].check(i, l, r, x, y)) res += t[ob].second[i].second;
    }
  }
  return res;
}
set<int> pos[N];
void change1(int p, int x) {
  if (nx[p] <= n) {
    t[idb[nx[p]]].upd(cur_id[nx[p]], pr[p]);
    pr[nx[p]] = pr[p];
  }
  pos[a[p]].erase(p);
  a[p] = x;
  pos[a[p]].insert(p);
  auto it = pos[x].upper_bound(p);
  if (it != pos[x].end()) {
    nx[p] = *it;
    pr[nx[p]] = p;
    t[idb[nx[p]]].upd(cur_id[nx[p]], p);
  } else
    nx[p] = n + 1;
  it = pos[x].lower_bound(p);
  if (it != pos[x].begin()) {
    --it;
    pr[p] = *it;
  } else
    pr[p] = 0;
  t[idb[p]].upd(cur_id[p], pr[p]);
}
void change2(int p, int x) {
  if (nx[p]) {
    t[idb[nx[p]]].upd(cur_id[nx[p]], pr[p]);
    pr[nx[p]] = pr[p];
  }
  pos[a[p]].erase(p);
  a[p] = x;
  pos[a[p]].insert(p);
  auto it = pos[x].upper_bound(p);
  if (it != pos[x].end())
    pr[p] = *it;
  else
    pr[p] = n + 1;
  t[idb[p]].upd(cur_id[p], pr[p]);
  it = pos[x].lower_bound(p);
  if (it != pos[x].begin()) {
    --it;
    nx[p] = *it;
    pr[nx[p]] = p;
    t[idb[nx[p]]].upd(cur_id[nx[p]], p);
  } else
    nx[p] = 0;
}
void deb() {
  for (int i = 1; i <= n; i++) {
    cout << t[idb[i]].second[cur_id[i]].first << ' ';
  }
  exit(0);
}
void solve() {
  n = get_int(), m = get_int();
  for (int i = 1; i <= n; i++) {
    a[i] = get_int();
    save[i] = a[i];
    pos[a[i]].insert(i);
    pr[i] = bfr[a[i]];
    bfr[a[i]] = i;
    idb[i] = i / block;
    cur_id[i] = t[idb[i]].ins(pr[i], i);
  }
  for (int i = 1; i <= n; i++) {
    bfr[a[i]] = n + 1;
  }
  for (int i = n; i >= 1; i--) {
    nx[i] = bfr[a[i]];
    bfr[a[i]] = i;
  }
  for (int i = 1; i <= m; i++) {
    type[i] = get_int(), l[i] = get_int(), r[i] = get_int();
    if (type[i] == 2) {
      ans[i] = get(l[i], r[i], 0, l[i] - 1);
    } else {
      if (a[l[i]] == r[i]) continue;
      change1(l[i], r[i]);
    }
  }
  for (int i = 0; i <= n / block; i++) t[i].clear();
  for (int i = 1; i <= n; i++) pos[i].clear();
  for (int i = 1; i <= n; i++) {
    a[i] = save[i];
    bfr[a[i]] = n + 1;
    pos[a[i]].insert(i);
  }
  for (int i = n; i >= 1; i--) {
    pr[i] = bfr[a[i]];
    bfr[a[i]] = i;
  }
  for (int i = 1; i <= n; i++) {
    bfr[a[i]] = 0;
  }
  for (int i = 1; i <= n; i++) {
    nx[i] = bfr[a[i]];
    bfr[a[i]] = i;
  }
  for (int i = 1; i <= n; i++) {
    t[idb[i]].ins(pr[i], i);
  }
  for (int i = 1; i <= m; i++) {
    if (type[i] == 2) {
      ans[i] = get(l[i], r[i], r[i] + 1, n + 1) - ans[i];
    } else {
      if (a[l[i]] == r[i]) continue;
      change2(l[i], r[i]);
    }
  }
  for (int i = 1; i <= m; i++)
    if (type[i] == 2) {
      printf("%I64d\n", ans[i]);
    }
}
int main() {
  cerr << sqrt(N) << '\n';
  int t = 1;
  while (t--) solve();
  exit(0);
}
