#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
void qread(int &x) {
  int neg = 1;
  x = 0;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') neg = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = 10 * x + c - '0', c = getchar();
  x *= neg;
}
const int maxn = 100005;
int n, q, cnt;
int a[maxn];
set<int> pos[maxn];
pair<int, int> b[maxn];
class Event {
 public:
  int tp, tm, l, r, val;
  Event(int _tp = 0, int _tm = 0, int _l = 0, int _r = 0, int _val = 0)
      : tp(_tp), tm(_tm), l(_l), r(_r), val(_val) {}
} e[maxn * 7], tmp[maxn * 7];
long long ans[maxn];
bool qry[maxn];
namespace Fenwick {
long long t[maxn];
void add(int v, long long val) {
  for (; v <= n; v += (v & -v)) t[v] += val;
}
long long sum(int v) {
  long long res = 0;
  for (; v; v -= (v & -v)) res += t[v];
  return res;
}
}  // namespace Fenwick
void solve(int l, int r) {
  if (l == r) return;
  int mid = l + r >> 1;
  solve(l, mid);
  solve(mid + 1, r);
  int pl = l, pr = mid + 1, pt = l;
  while (pl <= mid || pr <= r) {
    if (pr > r || pl <= mid && e[pl].l >= e[pr].l) {
      if (e[pl].tp == 0) Fenwick::add(e[pl].r, e[pl].val);
      tmp[pt++] = e[pl++];
    } else {
      if (e[pr].tp == 1)
        ans[e[pr].tm] += Fenwick::sum(e[pr].r) - Fenwick::sum(e[pr].l - 1);
      tmp[pt++] = e[pr++];
    }
  }
  for (int i = l; i <= mid; i++)
    if (e[i].tp == 0) Fenwick::add(e[i].r, -e[i].val);
  for (int i = l; i <= r; i++) e[i] = tmp[i];
}
int main() {
  qread(n);
  qread(q);
  for (int(i) = 1; (i) <= n; i++) {
    qread(a[i]);
    int last = pos[a[i]].empty() ? 0 : *pos[a[i]].rbegin();
    pos[a[i]].insert(i);
    if (last) {
      b[i] = make_pair(last, i - last);
      e[++cnt] = Event(0, 0, b[i].first, i, b[i].second);
    }
  }
  for (int(i) = 1; (i) <= n; i++) pos[i].insert(0), pos[i].insert(n + 1);
  for (int(i) = 1; (i) <= q; i++) {
    int tp, x, y;
    qread(tp);
    qread(x);
    qread(y);
    if (tp == 1) {
      set<int>::iterator it = pos[a[x]].lower_bound(x), it2 = it, it3 = it;
      int prv = *(--it2), nxt = *(++it3);
      if (prv >= 1) e[++cnt] = Event(0, i, b[x].first, x, -b[x].second);
      if (nxt <= n) e[++cnt] = Event(0, i, b[nxt].first, nxt, -b[nxt].second);
      if (prv >= 1 && nxt <= n) {
        b[nxt] = make_pair(prv, nxt - prv);
        e[++cnt] = Event(0, i, b[nxt].first, nxt, b[nxt].second);
      }
      pos[a[x]].erase(it);
      a[x] = y;
      pos[a[x]].insert(x);
      it = pos[a[x]].lower_bound(x);
      it2 = it;
      it3 = it;
      prv = *(--it2);
      nxt = *(++it3);
      if (prv >= 1 && nxt <= n)
        e[++cnt] = Event(0, i, b[nxt].first, nxt, -b[nxt].second);
      if (prv >= 1) {
        b[x] = make_pair(prv, x - prv);
        e[++cnt] = Event(0, i, b[x].first, x, b[x].second);
      }
      if (nxt <= n) {
        b[nxt] = make_pair(x, nxt - x);
        e[++cnt] = Event(0, i, b[nxt].first, nxt, b[nxt].second);
      }
    } else {
      qry[i] = true;
      e[++cnt] = Event(1, i, x, y, 0);
    }
  }
  solve(1, cnt);
  for (int(i) = 1; (i) <= q; i++)
    if (qry[i]) printf("%lld\n", ans[i]);
  return 0;
}
