#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
set<int> se[N];
int st[150][4 * N], a[N], bs = 1000;
int pre(int x) {
  int ele = a[x];
  auto it = se[ele].lower_bound(x);
  if (it == se[ele].begin()) return -1;
  it--;
  return *it;
}
int nex(int x) {
  int ele = a[x];
  auto it = se[ele].upper_bound(x);
  if (it == se[ele].end()) return -1;
  return *it;
}
void update(int nn, int ss, int se, int ind, int val, int i) {
  if (ss > se || ind > se || ind < ss) return;
  if (ss == se) {
    st[nn][i] = val;
    return;
  }
  int mid = (ss + se) / 2;
  update(nn, ss, mid, ind, val, 2 * i + 1);
  update(nn, mid + 1, se, ind, val, 2 * i + 2);
  st[nn][i] = st[nn][2 * i + 1] + st[nn][2 * i + 2];
}
int query(int nn, int ss, int se, int l, int r, int i) {
  if (ss > se || l > se || r < ss) return 0;
  if (l <= ss && se <= r) return st[nn][i];
  int mid = (ss + se) / 2;
  return query(nn, ss, mid, l, r, 2 * i + 1) +
         query(nn, mid + 1, se, l, r, 2 * i + 2);
}
void upd(int x, int n) {
  if (x == -1) return;
  int p = pre(x);
  if (p == -1) return;
  update(x / bs, 0, n - 1, p, x - p, 0);
}
int main() {
  int n, m, i;
  scanf("%d%d", &n, &m);
  for (i = 0; i < n; i++) {
    scanf("%d", a + i);
    se[a[i]].insert(i);
  }
  for (i = 0; i < n; i++) {
    int x = pre(i);
    if (x != -1) update(i / bs, 0, n - 1, x, i - x, 0);
  }
  while (m--) {
    int ty, p, x, l, r;
    scanf("%d", &ty);
    if (ty == 1) {
      scanf("%d%d", &p, &x);
      p--;
      int n1, n2;
      n1 = nex(p);
      se[a[p]].erase(p);
      a[p] = x;
      se[x].insert(p);
      n2 = nex(p);
      upd(p, n);
      upd(n1, n);
      upd(n2, n);
    } else {
      scanf("%d%d", &l, &r);
      l--;
      r--;
      long long ans = 0;
      for (i = l; i <= r;) {
        if (i % bs == 0 && i + bs <= r + 1) {
          ans += query(i / bs, 0, n - 1, l, n - 1, 0);
          i += bs;
        } else {
          int pp = pre(i);
          if (pp >= l) ans += i - pp;
          i++;
        }
      }
      printf("%lld\n", ans);
    }
  }
}
