#include <bits/stdc++.h>
const long long mod = 1e9 + 7;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
using namespace std;
const int N = 1e5 + 1, M = 1e7 + 1;
set<int> s[N];
set<int>::iterator p, p1, p2;
int a[N], n, m;
struct node {
  int l, r, ls, rs, s;
  node() { ls = rs = s = 0; }
} h[M];
int tot, root[N];
void update(int &t, int l, int r, int y, int x) {
  if (t == 0) t = ++tot;
  h[t].l = l, h[t].r = r, h[t].s += x;
  if (l == r) return;
  int mid = (l + r) / 2;
  if (y <= mid)
    update(h[t].ls, l, mid, y, x);
  else
    update(h[t].rs, mid + 1, r, y, x);
}
long long query(int t, int l, int r) {
  if (t == 0) return 0;
  if (h[t].l >= l && h[t].r <= r) {
    return h[t].s;
  }
  int mid = (h[t].l + h[t].r) / 2;
  long long ans = 0;
  if (l <= mid) ans += query(h[t].ls, l, r);
  if (r > mid) ans += query(h[t].rs, l, r);
  return ans;
}
void add(int x, int y, int z) {
  if (x < 1 || y < 1 || x > n || y > n) return;
  for (; x <= n; x += x & -x) update(root[x], 1, n, y, z);
}
long long sum(int x, int y, int z) {
  long long ans = 0;
  for (; x > 0; x -= x & -x) ans += query(root[x], y, z);
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(0);
  srand(time(0));
  cin >> n >> m;
  for (int i = 1; i <= n; i++) s[i].insert(0), s[i].insert(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    s[a[i]].insert(i);
    p1 = p2 = p = s[a[i]].find(i);
    add(i, *(--p1), i - *(--p2));
  }
  while (m--) {
    int op, aa, bb;
    cin >> op >> aa >> bb;
    if (op == 1) {
      p1 = p2 = p = s[a[aa]].find(aa);
      p1--, p2++;
      add(aa, *p1, *p1 - aa);
      add(*p2, aa, aa - *p2);
      add(*p2, *p1, *p2 - *p1);
      s[a[aa]].erase(p);
      a[aa] = bb;
      s[bb].insert(aa);
      p1 = p2 = p = s[bb].find(aa);
      p1--, p2++;
      add(aa, *p1, aa - *p1);
      add(*p2, aa, *p2 - aa);
      add(*p2, *p1, *p1 - *p2);
    } else
      cout << sum(bb, aa, bb) - sum(aa - 1, aa, bb) << endl;
  }
  return 0;
}
