#include <bits/stdc++.h>
using namespace std;
const int N = 101010;
int n, m;
int a[N], pre[N], Pre[N], b[N];
pair<int, pair<int, int> > q[N];
set<int> s[N];
vector<int> v[N << 2];
long long tot[N << 2];
vector<long long> sum[N << 2];
void build(int l, int r, int rt) {
  for (int i = (l); i < (r + 1); ++i) v[rt].push_back(pre[i]);
  if (l == r) return;
  int mid = l + r >> 1;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
}
void upd(int p, int c, int l, int r, int rt) {
  if (!c) return;
  v[rt].push_back(c);
  if (l == r) return;
  int mid = l + r >> 1;
  if (p <= mid)
    upd(p, c, l, mid, rt << 1);
  else
    upd(p, c, mid + 1, r, rt << 1 | 1);
}
void upd(int rt, int p, long long c) {
  if (!p) return;
  p = lower_bound(v[rt].begin(), v[rt].end(), p) - v[rt].begin() + 1;
  tot[rt] += c;
  for (; p <= (int)v[rt].size(); p += ((p) & -(p))) sum[rt][p] += c;
}
long long qry(int rt, int p) {
  p = lower_bound(v[rt].begin(), v[rt].end(), p) - v[rt].begin();
  long long res = tot[rt];
  for (; p >= 1; p ^= ((p) & -(p))) res -= sum[rt][p];
  return res;
}
void build2(int l, int r, int rt) {
  sort(v[rt].begin(), v[rt].end());
  v[rt].erase(unique(v[rt].begin(), v[rt].end()), v[rt].end());
  sum[rt] = vector<long long>((int)v[rt].size() + 1);
  for (int i = (l); i < (r + 1); ++i) upd(rt, pre[i], i - pre[i]);
  if (l == r) return;
  int mid = l + r >> 1;
  build2(l, mid, rt << 1);
  build2(mid + 1, r, rt << 1 | 1);
}
void upd(int p, int v1, long long v2, int l, int r, int rt) {
  if (!v1) return;
  upd(rt, v1, v2);
  if (l == r) return;
  int mid = l + r >> 1;
  if (p <= mid)
    upd(p, v1, v2, l, mid, rt << 1);
  else
    upd(p, v1, v2, mid + 1, r, rt << 1 | 1);
}
long long qry(int L, int R, int c, int l, int r, int rt) {
  if (L <= l && r <= R) return qry(rt, c);
  int mid = l + r >> 1;
  long long res = 0;
  if (L <= mid) res += qry(L, R, c, l, mid, rt << 1);
  if (R > mid) res += qry(L, R, c, mid + 1, r, rt << 1 | 1);
  return res;
}
int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);
  cin >> n >> m;
  for (int i = (1); i < (n + 1); ++i)
    cin >> a[i], pre[i] = Pre[a[i]], Pre[a[i]] = i;
  for (int i = (1); i < (m + 1); ++i)
    cin >> q[i].first >> q[i].second.first >> q[i].second.second;
  build(1, n, 1);
  for (int i = (1); i < (N); ++i) s[i].insert(0);
  for (int i = (1); i < (n + 1); ++i) s[a[i]].insert(i), b[i] = a[i];
  for (int i = (1); i < (m + 1); ++i)
    if (q[i].first == 1) {
      int p = q[i].second.first, c = q[i].second.second;
      auto t = s[b[p]].lower_bound(p), ne = t, pre = t;
      --pre, ++ne;
      if (ne != s[b[p]].end()) upd(*ne, *pre, 1, n, 1);
      s[b[p]].erase(t);
      s[c].insert(p);
      t = s[c].lower_bound(p), ne = t, pre = t;
      --pre, ++ne;
      if (ne != s[c].end()) upd(*ne, p, 1, n, 1);
      upd(p, *pre, 1, n, 1);
      b[p] = c;
    }
  build2(1, n, 1);
  for (int i = (1); i < (N); ++i) s[i].clear(), s[i].insert(0);
  for (int i = (1); i < (n + 1); ++i) s[a[i]].insert(i), b[i] = a[i];
  for (int i = (1); i < (m + 1); ++i) {
    if (q[i].first == 1) {
      int p = q[i].second.first, c = q[i].second.second;
      auto t = s[b[p]].lower_bound(p), ne = t, pre = t;
      --pre, ++ne;
      if (ne != s[b[p]].end()) {
        upd(*ne, *t, -(*ne - *t), 1, n, 1);
        upd(*ne, *pre, *ne - *pre, 1, n, 1);
      }
      upd(*t, *pre, -(*t - *pre), 1, n, 1);
      s[b[p]].erase(t);
      s[c].insert(p);
      t = s[c].lower_bound(p), ne = t, pre = t;
      --pre, ++ne;
      if (ne != s[c].end()) {
        upd(*ne, *pre, -(*ne - *pre), 1, n, 1);
        upd(*ne, p, *ne - p, 1, n, 1);
      }
      upd(p, *pre, p - *pre, 1, n, 1);
      b[p] = c;
    } else {
      int l = q[i].second.first, r = q[i].second.second;
      cout << qry(l, r, l, 1, n, 1) << "\n";
    }
  }
  return 0;
}
