#include <bits/stdc++.h>
using namespace std;
const int block = 2000;
int n, m, a[1000000], pre[1000000], nex[1000000], val[1000000], m1, m2;
long long ans[1000000];
set<int> s[1000000];
struct arr {
  int l, r, z, num;
} ask[1000000];
struct arrr {
  int x, y;
} upd[1000000];
struct segment_tree {
  long long a[1000000];
  void update(int l, int r, int k, int x, int y) { a[x] += y; }
  long long find(int l, int r, int k, int x, int y) {
    long long ans = 0;
    for (int i = x; i <= y; i++) ans += a[i];
    return ans;
  }
} f;
bool cmp(arr x, arr y) {
  if ((x.l - 1) / block != (y.l - 1) / block)
    return (x.l - 1) / block < (y.l - 1) / block;
  if ((x.r - 1) / block != (y.r - 1) / block)
    return (x.r - 1) / block < (y.r - 1) / block;
  return x.z < y.z;
}
int main() {
  scanf("%d%d", &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++) {
    scanf("%d", &a[i]);
    s[a[i]].insert(i);
  }
  for (int i = 1; i <= n; i++) {
    val[i] = pre[i] = *(--s[a[i]].lower_bound(i));
    nex[i] = *(s[a[i]].upper_bound(i));
  }
  for (int i = 1; i <= m; i++) {
    int bo, x, y;
    scanf("%d%d%d", &bo, &x, &y);
    if (bo & 1) {
      if (a[x] != y) {
        int xx = *(--s[y].lower_bound(x)), yy = *(s[y].upper_bound(x));
        s[a[x]].erase(x);
        s[y].insert(x);
        a[x] = y;
        if (nex[x] != n + 1) {
          pre[nex[x]] = pre[x];
          upd[++m2] = {nex[x], pre[nex[x]]};
        }
        if (pre[x] != 0) nex[pre[x]] = nex[x];
        if (xx != 0) nex[xx] = x;
        if (yy != n + 1) {
          pre[yy] = x;
          upd[++m2] = {yy, pre[yy]};
        }
        pre[x] = xx;
        nex[x] = yy;
        upd[++m2] = {x, pre[x]};
      }
    } else
      ask[++m1] = {x, y, m2, m1};
  }
  sort(ask + 1, ask + m1 + 1, cmp);
  int l = 1, r = 0, z = 0;
  for (int i = 1; i <= m1; i++) {
    while (l < ask[i].l) {
      f.update(1, n, 1, val[l], val[l] - l);
      ++l;
    }
    while (l > ask[i].l) {
      --l;
      f.update(1, n, 1, val[l], l - val[l]);
    }
    while (r < ask[i].r) {
      ++r;
      f.update(1, n, 1, val[r], r - val[r]);
    }
    while (r > ask[i].r) {
      f.update(1, n, 1, val[r], val[r] - r);
      --r;
    }
    while (z < ask[i].z) {
      ++z;
      if (l <= upd[z].x && upd[z].x <= r) {
        f.update(1, n, 1, val[upd[z].x], val[upd[z].x] - upd[z].x);
        f.update(1, n, 1, upd[z].y, upd[z].x - upd[z].y);
      }
      swap(upd[z].y, val[upd[z].x]);
    }
    while (z > ask[i].z) {
      if (l <= upd[z].x && upd[z].x <= r) {
        f.update(1, n, 1, val[upd[z].x], val[upd[z].x] - upd[z].x);
        f.update(1, n, 1, upd[z].y, upd[z].x - upd[z].y);
      }
      swap(upd[z].y, val[upd[z].x]);
      --z;
    }
    ans[ask[i].num] = f.find(1, n, 1, ask[i].l, n);
  }
  for (int i = 1; i <= m1; i++) printf("%lld\n", ans[i]);
}
