#include <bits/stdc++.h>
using namespace std;
namespace IOstream {
template <typename T>
inline void read(T &x) {
  x = 0;
  T fl = 1;
  char c = 0;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') fl = -1;
  for (; c >= '0' && c <= '9'; c = getchar())
    x = (x << 1) + (x << 3) + (c ^ 48);
  x *= fl;
}
}  // namespace IOstream
using namespace IOstream;
const int N = 100000 + 6;
set<int> st[N];
int n, m;
int rt[N], a[N], fst[N];
namespace seg {
int ntot = 0;
struct node {
  int lc, rc;
  long long s;
  node() { lc = rc = s = 0; }
} tr[N * 120];
void upd(int &nod, int l, int r, int k, long long val) {
  if (!nod) nod = ++ntot;
  tr[nod].s += val;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (k <= mid)
    upd(tr[nod].lc, l, mid, k, val);
  else
    upd(tr[nod].rc, mid + 1, r, k, val);
}
long long query(int nod, int l, int r, int k) {
  if (!nod) return 0;
  if (l == r) return tr[nod].s;
  int mid = (l + r) >> 1;
  if (k <= mid)
    return query(tr[nod].lc, l, mid, k) + tr[tr[nod].rc].s;
  else
    return query(tr[nod].rc, mid + 1, r, k);
}
}  // namespace seg
namespace BIT_TREE {
void add(int k, int q, long long val, int n) {
  for (int i = k; i <= n; i += (i & -i)) seg::upd(rt[i], 1, n, q, val);
}
long long sum(int k, int q, int n) {
  long long res = 0ll;
  for (int i = q; i; i -= (i & -i)) res += seg::query(rt[i], 1, n, k);
  return res;
}
}  // namespace BIT_TREE
set<int>::iterator lst(set<int>::iterator it) { return --it; }
set<int>::iterator nxt(set<int>::iterator it) { return ++it; }
void upd(int x, int y, int n) {
  if (fst[x]) BIT_TREE::add(x, fst[x], fst[x] - x, n);
  if (y) BIT_TREE::add(x, y, x - y, n);
  fst[x] = y;
}
int main() {
  read(n);
  read(m);
  for (int i = 1; i <= n; i++) read(a[i]);
  for (int i = 1; i <= n; i++) {
    if (st[a[i]].size()) {
      fst[i] = *st[a[i]].rbegin();
      BIT_TREE::add(i, fst[i], i - fst[i], n);
    }
    st[a[i]].insert(i);
  }
  while (m--) {
    int opt, x, y;
    read(opt);
    read(x);
    read(y);
    if (opt == 1) {
      set<int>::iterator it = st[a[x]].find(x);
      if (nxt(it) != st[a[x]].end())
        upd(*nxt(it), (it == st[a[x]].begin() ? 0 : *lst(it)), n);
      st[a[x]].erase(x);
      a[x] = y;
      it = st[y].insert(x).first;
      upd(x, (it == st[y].begin() ? 0 : *lst(it)), n);
      if (nxt(it) != st[y].end()) upd(*nxt(it), x, n);
    } else {
      printf("%lld\n", BIT_TREE::sum(x, y, n));
    }
  }
  return 0;
}
