#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
set<int> s[MAXN];
set<int>::iterator it;
int pre[MAXN], nxt[MAXN];
long long ans[MAXN];
struct Seg {
  bool is;
  int x, y, val, pos;
  bool operator<(const Seg &a) const {
    if (is != a.is) return is < a.is;
    if (is) return y < a.y;
    return x < a.x;
  }
} q[MAXN << 3];
int hs, n, m, a[MAXN], tot;
template <class T>
void rd(T &x) {
  char c = getchar();
  for (; c > '9' || c < '0'; c = getchar())
    ;
  for (x = 0; c >= '0' && c <= '9'; c = getchar())
    x = (x << 3) + (x << 1) + (c ^ 48);
}
struct BIT {
  long long c[MAXN];
  void add(int x, long long v) {
    if (!x) return;
    for (; x <= n; x += (x & -x)) c[x] += v;
  }
  long long query(int x) {
    long long res = 0;
    while (x) res += c[x], x -= x & -x;
    return res;
  }
} T;
void fix(int x, int v) {
  q[++hs] = (Seg){0, x, pre[x], pre[x] - x, 0};
  pre[x] = v;
  q[++hs] = (Seg){0, x, pre[x], x - v, 0};
}
void solve(int l, int r) {
  if (l == r) return;
  int mid = l + r >> 1;
  solve(l, mid);
  solve(mid + 1, r);
  int ql = l - 1, qr = mid + 1;
  for (; qr <= r; qr++)
    if (q[qr].is) {
      while (ql < mid && (q[ql + 1].is || q[ql + 1].x <= q[qr].y)) {
        ql++;
        if (q[ql].is == 0) T.add(q[ql].y, q[ql].val);
      }
      ans[q[qr].pos] += T.query(n) - T.query(q[qr].x - 1);
    }
  for (int i = l; i <= ql; i++)
    if (q[i].is == 0) T.add(q[i].y, -q[i].val);
  sort(q + l, q + r + 1);
}
int getnxt(int pos, int v) {
  it = s[v].upper_bound(pos);
  return *it;
}
int getpre(int pos, int v) {
  it = s[v].lower_bound(pos);
  it--;
  return *it;
}
int main() {
  rd(n);
  rd(m);
  for (int i = 1; i <= n; i++) s[i].insert(0), s[i].insert(n + 1);
  for (int i = 1; i <= n; i++) rd(a[i]), s[a[i]].insert(i);
  for (int i = 1; i <= n; i++)
    pre[i] = getpre(i, a[i]), nxt[i] = getnxt(i, a[i]),
    q[++hs] = (Seg){0, i, pre[i], i - pre[i], 0};
  for (int i = 1, tp, x, y; i <= m; i++) {
    rd(tp);
    rd(x);
    rd(y);
    if (tp == 1) {
      if (y == a[x]) continue;
      int newpre = getpre(x, y), newnxt = getnxt(x, y);
      s[a[x]].erase(x);
      s[y].insert(x);
      a[x] = y;
      if (nxt[x] != n + 1) fix(nxt[x], pre[x]);
      if (pre[x] != 0) nxt[pre[x]] = nxt[x];
      if (newpre != 0) nxt[newpre] = x;
      if (newnxt != n + 1) fix(newnxt, x);
      fix(x, newpre);
      nxt[x] = newnxt;
    } else
      ++tot, q[++hs] = (Seg){1, x, y, 0, tot};
  }
  solve(1, hs);
  for (int i = 1; i <= tot; i++) printf("%lld\n", ans[i]);
  return 0;
}
