#include <bits/stdc++.h>
using namespace std;
int n, q, l, r, type;
namespace bit {
long long a[100010];
void add(int loc, int val) {
  for (int i = loc; i <= n; i += (i & (-i))) a[i] += val;
}
long long query(int l, int r) {
  long long ret = 0;
  for (int i = l - 1; i > 0; i -= (i & (-i))) ret -= a[i];
  for (int i = r; i > 0; i -= (i & (-i))) ret += a[i];
  return ret;
}
}  // namespace bit
using namespace bit;
struct info {
  int x, y, l, r, xis, val, num;
  bool operator<(const info &a) const { return x < a.x; }
};
info sth[1000010];
info lef[1000010], rig[1000010];
int num[100010], ocnt, acnt;
long long ans[100010];
set<int> kk[100010];
void supdiv(int pl, int pr, int vl, int vr) {
  int lcnt = 0, rcnt = 0, tcnt = 0;
  if (vl == vr) {
    for (int i = pl; i <= pr; ++i) {
      if (!sth[i].y)
        ans[sth[i].num] += sth[i].xis * query(sth[i].l, sth[i].r);
      else
        add(sth[i].y, sth[i].val);
    }
    for (int i = pl; i <= pr; ++i)
      if (sth[i].y) add(sth[i].y, -sth[i].val);
    return;
  }
  int mid = vl + vr >> 1;
  for (int i = pl; i <= pr; ++i) {
    if (sth[i].x <= mid) {
      if (sth[i].y) add(sth[i].y, sth[i].val);
      lef[++lcnt] = sth[i];
    } else {
      if (!sth[i].y) ans[sth[i].num] += sth[i].xis * query(sth[i].l, sth[i].r);
      rig[++rcnt] = sth[i];
    }
  }
  for (int i = 1; i <= lcnt; ++i)
    if (lef[i].y) add(lef[i].y, -lef[i].val);
  for (int i = 1; i <= lcnt; ++i) sth[pl + (tcnt++)] = lef[i];
  for (int i = 1; i <= rcnt; ++i) sth[pl + (tcnt++)] = rig[i];
  supdiv(pl, pl + lcnt - 1, vl, mid), supdiv(pl + lcnt, pr, mid + 1, vr);
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; ++i) scanf("%d", &num[i]), kk[num[i]].insert(i);
  for (int i = 1; i <= n; ++i) {
    if (kk[i].size() >= 2) {
      int pre;
      set<int>::iterator nloc;
      nloc = kk[i].begin(), pre = *nloc, nloc++;
      while (nloc != kk[i].end()) {
        sth[++ocnt] = {pre, *nloc, 0, 0, 0, *nloc - pre, 0};
        pre = *nloc, nloc++;
      }
    }
  }
  for (int i = 1; i <= q; ++i) {
    scanf("%d%d%d", &type, &l, &r);
    if (type == 2) {
      sth[++ocnt] = {l - 1, 0, l, r, -1, 0, ++acnt};
      sth[++ocnt] = {r, 0, l, r, 1, 0, acnt};
    } else {
      set<int>::iterator nloc = kk[num[l]].find(l);
      int op = 0, pre, nex;
      if (nloc != kk[num[l]].begin()) {
        nloc--;
        pre = *nloc;
        ++op, nloc++;
        sth[++ocnt] = {pre, l, 0, 0, 0, pre - l, 0};
      }
      nloc = kk[num[l]].find(l), nloc++;
      if (nloc != kk[num[l]].end()) {
        nex = *nloc;
        ++op;
        sth[++ocnt] = {l, nex, 0, 0, 0, l - nex, 0};
      }
      nloc = kk[num[l]].find(l);
      kk[num[l]].erase(nloc);
      if (op == 2) sth[++ocnt] = {pre, nex, 0, 0, 0, nex - pre, 0};
      op = 0, num[l] = r, nloc = (kk[r].insert(l).first);
      if (nloc != kk[r].begin()) {
        nloc--, pre = *nloc, nloc++, op++;
        sth[++ocnt] = {pre, l, 0, 0, 0, l - pre, 0};
      }
      nloc++;
      if (nloc != kk[r].end()) {
        nex = *nloc, op++;
        sth[++ocnt] = {l, nex, 0, 0, 0, nex - l, 0};
      }
      if (op == 2) sth[++ocnt] = {pre, nex, 0, 0, 0, pre - nex, 0};
    }
  }
  supdiv(1, ocnt, 0, n);
  for (int i = 1; i <= acnt; ++i) printf("%lld\n", ans[i]);
  return 0;
}
