#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
set<int> se[N];
int st[105][4 * N], a[N], bs = 1000, prevv[N];
int pre(int x) {
  int ele = a[x];
  auto it = se[ele].lower_bound(x);
  if (it == se[ele].begin()) return prevv[x] = -1;
  it--;
  return prevv[x] = *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);
}
void rest(int x, int n) {
  if (x == -1) return;
  int p = pre(x);
  if (p == -1) return;
  update(x / bs, 0, n - 1, p, 0, 0);
}
void print(int n) {
  int i, j;
  for (i = 0; i < n; i += bs) {
    cout << i / bs << "th block" << endl;
    for (j = 0; j < n; j++) {
      cout << query(i / bs, 0, n - 1, j, j, 0) << " ";
    }
    cout << endl;
  }
}
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--;
      rest(p, n);
      int n1, n2;
      n1 = nex(p);
      rest(n1, n);
      swap(a[p], x);
      n2 = nex(p);
      rest(n2, n);
      swap(a[p], x);
      se[a[p]].erase(p);
      a[p] = x;
      se[x].insert(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 {
          if (prevv[i] >= l) ans += i - prevv[i];
          i++;
        }
      }
      printf("%lld\n", ans);
    }
  }
}
