#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100005;
vector<int> go[N];
vector<ll> ft[N];
void prec_add(int x, int y) {
  for (; x < N; x += x & -x) {
    go[x].push_back(y);
  }
}
void init() {
  for (int i = 1; i < N; i++) {
    sort(go[i].begin(), go[i].end());
    go[i].resize(unique(go[i].begin(), go[i].end()) - go[i].begin());
    ft[i].assign(go[i].size() + 1, 0);
  }
}
void add(int x, int y, int val) {
  for (; x < N; x += x & -x) {
    int id = int(upper_bound(go[x].begin(), go[x].end(), y) - go[x].begin());
    for (; id < (int)ft[x].size(); id += id & -id) ft[x][id] += val;
  }
}
ll sum(int x, int y) {
  ll ans = 0;
  for (; x > 0; x -= x & -x) {
    int id = int(upper_bound(go[x].begin(), go[x].end(), y) - go[x].begin());
    for (; id > 0; id -= id & -id) ans += ft[x][id];
  }
  return ans;
}
int n, m;
int a[N], ta[N];
int t[N], l[N], r[N];
set<int> occ[N];
vector<tuple<int, int, int>> upd(int pos, int val) {
  vector<tuple<int, int, int>> ans;
  if (a[pos] == val) return ans;
  {
    auto it = occ[a[pos]].find(pos);
    bool to_add = true;
    if (it != occ[a[pos]].begin()) {
      ans.emplace_back(*prev(it), *it, -1);
    } else
      to_add = false;
    if (next(it) != occ[a[pos]].end()) {
      ans.emplace_back(*it, *next(it), -1);
    } else
      to_add = false;
    if (to_add) {
      ans.emplace_back(*prev(it), *next(it), 1);
    }
    occ[a[pos]].erase(it);
  }
  {
    a[pos] = val;
    occ[a[pos]].insert(pos);
    auto it = occ[a[pos]].find(pos);
    bool to_add = true;
    if (it != occ[a[pos]].begin()) {
      ans.emplace_back(*prev(it), *it, 1);
    } else
      to_add = false;
    if (next(it) != occ[a[pos]].end()) {
      ans.emplace_back(*it, *next(it), 1);
    } else
      to_add = false;
    if (to_add) {
      ans.emplace_back(*prev(it), *next(it), -1);
    }
  }
  return ans;
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    if (!occ[a[i]].empty()) {
      prec_add(*occ[a[i]].rbegin(), i);
    }
    occ[a[i]].insert(i);
    ta[i] = a[i];
  }
  for (int i = 0; i < m; i++) {
    scanf("%d %d %d", t + i, l + i, r + i);
    if (t[i] == 1) {
      for (auto [x, y, val] : upd(l[i], r[i])) {
        prec_add(x, y);
      }
    }
  }
  init();
  for (int i = 1; i <= n; i++) occ[i].clear();
  for (int i = 1; i <= n; i++) {
    a[i] = ta[i];
    if (!occ[a[i]].empty()) {
      int lef = *occ[a[i]].rbegin();
      add(lef, i, i - lef);
    }
    occ[a[i]].insert(i);
  }
  for (int i = 0; i < m; i++) {
    if (t[i] == 1) {
      for (auto [x, y, val] : upd(l[i], r[i])) {
        add(x, y, val * (y - x));
      }
    } else {
      ll ans = sum(r[i], r[i]);
      ans -= sum(l[i] - 1, r[i]);
      ans -= sum(r[i], l[i] - 1);
      ans += sum(l[i] - 1, l[i] - 1);
      printf("%lld\n", ans);
    }
  }
}
