#include <bits/stdc++.h>
using namespace std;
int rt[100100], lc[15000000], rc[15000000], tot;
long long c[15000000];
int n, q;
int a[100100];
int las[100100], le[100100], ri[100100];
set<int> s[100100];
set<int>::iterator it;
struct Bit {
  long long bit[100100];
  void init() {
    for (int i = 0; i <= n; ++i) bit[i] = 0;
  }
  void add(int pos, int val) {
    if (!val) return;
    while (pos <= n) {
      bit[pos] += val;
      pos += pos & (-pos);
    }
  }
  long long sum(int pos) {
    long long ret = 0;
    while (pos > 0) {
      ret += bit[pos];
      pos -= pos & (-pos);
    }
    return ret;
  }
  long long seg(int l, int r) { return sum(r) - sum(l - 1); }
} bt;
void ins(int &o, int l, int r, int pos, int val) {
  if (!o) o = ++tot;
  c[o] += val;
  if (l == r) return;
  if (pos <= ((l + r) >> 1))
    ins(lc[o], l, ((l + r) >> 1), pos, val);
  else
    ins(rc[o], ((l + r) >> 1) + 1, r, pos, val);
}
long long query(int o, int l, int r, int y1, int y2) {
  if (!o) return 0;
  if (y1 <= l && y2 >= r) return c[o];
  long long ans = 0;
  if (y1 <= ((l + r) >> 1)) ans += query(lc[o], l, ((l + r) >> 1), y1, y2);
  if (y2 > ((l + r) >> 1)) ans += query(rc[o], ((l + r) >> 1) + 1, r, y1, y2);
  return ans;
}
long long ask(int pos, int l, int r) {
  long long ans = 0;
  if (l > r) return 0;
  while (pos > 0) {
    ans += query(rt[pos], 1, n, l, r);
    pos -= pos & (-pos);
  }
  return ans;
}
void deal(int x, int pos, int val) {
  if (!val) return;
  while (x <= n) {
    ins(rt[x], 1, n, pos, val);
    x += x & (-x);
  }
}
void output() {
  for (int i = 1; i <= n; ++i) printf("%d%c", a[i], i == n ? '\n' : ' ');
  for (int i = 1; i <= n; ++i)
    printf("le[%d]=%d,ri[%d]=%d\n", i, le[i], i, ri[i]);
}
void change(int pos, int val) {
  if (a[pos] == val) return;
  int lef = le[pos], rig = ri[pos];
  bt.add(pos, -(pos - lef));
  bt.add(rig, -(rig - pos));
  if (lef != pos && rig != pos) bt.add(rig, rig - lef);
  deal(pos, lef, pos - lef);
  deal(rig, pos, rig - pos);
  if (lef != pos && rig != pos) deal(rig, lef, lef - rig);
  le[rig] = lef;
  ri[lef] = rig;
  if (le[rig] == pos) le[rig] = rig;
  if (ri[lef] == pos) ri[lef] = lef;
  s[a[pos]].erase(pos);
  s[val].insert(pos);
  it = s[val].find(pos);
  if (it == s[val].begin())
    lef = pos;
  else {
    --it;
    lef = (*it);
    ++it;
  }
  rig = (++it == s[val].end() ? pos : (*it));
  if (lef != pos && rig != pos) bt.add(rig, -(rig - lef));
  bt.add(pos, pos - lef);
  bt.add(rig, rig - pos);
  if (lef != pos && rig != pos) deal(rig, lef, rig - lef);
  deal(pos, lef, lef - pos);
  deal(rig, pos, pos - rig);
  ri[lef] = pos;
  le[rig] = pos;
  le[pos] = lef;
  ri[pos] = rig;
  a[pos] = val;
}
int main() {
  scanf("%d%d", &n, &q);
  bt.init();
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    if (las[a[i]]) {
      bt.add(i, i - las[a[i]]);
      le[i] = las[a[i]];
      ri[las[a[i]]] = i;
    } else {
      le[i] = i;
    }
    las[a[i]] = i;
    s[a[i]].insert(i);
    deal(i, le[i], le[i] - i);
  }
  for (int i = 1; i <= n; ++i)
    if (las[i]) ri[las[i]] = las[i];
  while (q--) {
    int op, l, r;
    scanf("%d%d%d", &op, &l, &r);
    if (op == 1)
      change(l, r);
    else {
      long long ans = bt.seg(l, r);
      ans += ask(r, 1, l - 1) - ask(l - 1, 1, l - 1);
      printf("%I64d\n", ans);
    }
  }
  return 0;
}
