#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
struct Query {
  int id, opt, x, y, val;
} p[N], q[N];
int n, m, w[N], ans[N], tot;
inline int read() {
  int s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') f = ch == '-' ? -1 : f, ch = getchar();
  while (ch >= '0' && ch <= '9')
    s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
  return s * f;
}
set<int> st[N];
set<int>::iterator it;
int pre[N], nxt[N], mk[N];
inline int get_pre(int id) {
  it = st[w[id]].lower_bound(id);
  it--;
  return *it;
}
inline int get_nxt(int id) { return *(it = st[w[id]].upper_bound(id)); }
inline bool cmp(Query a, Query b) { return a.x > b.x; }
inline bool cmp1(Query a, Query b) { return a.id < b.id; }
int c[N];
inline int lowbit(int x) { return x & -x; }
inline void add(int x, int w) {
  while (x <= n) {
    c[x] += w;
    x += lowbit(x);
  }
}
inline int sum(int x, int res = 0) {
  while (x > 0) {
    res += c[x];
    x -= lowbit(x);
  }
  return res;
}
inline void debug(int l, int r) {
  for (int i = l; i <= r; ++i)
    printf("i=%d id=%d opt=%d x=%d y=%d val=%d  ans=%d\n", i, q[i].id, q[i].opt,
           q[i].x, q[i].y, q[i].val, ans[q[i].id]);
}
void cdq(int l, int r) {
  if (l == r) return;
  int mid = l + r >> 1;
  cdq(l, mid), cdq(mid + 1, r);
  int ql = l, qr = mid + 1, tt = l;
  sort(q + l, q + mid + 1, cmp);
  sort(q + mid + 1, q + r + 1, cmp);
  for (int i = mid + 1; i <= r; ++i) {
    while (ql <= mid && q[ql].x >= q[i].x) {
      if (q[ql].opt == 2) {
        ql++;
        continue;
      }
      mk[ql] = 1;
      add(q[ql].y, q[ql].val);
      ql++;
    }
    if (q[i].opt == 2) ans[q[i].id] += sum(q[i].y) - sum(q[i].x - 1);
  }
  for (int i = l; i <= mid; ++i)
    if (mk[i]) mk[i] = 0, add(q[i].y, -q[i].val);
}
int main() {
  n = read(), m = read();
  for (int i = 1; i <= n; ++i) w[i] = read(), st[w[i]].insert(i);
  for (int i = 1; i <= n; ++i) st[i].insert(0), st[i].insert(n + 1);
  for (int i = 1; i <= n; ++i)
    pre[i] = get_pre(i), nxt[i] = get_nxt(i),
    q[++tot] = {0, 1, pre[i], i, i - pre[i]};
  for (int i = 1; i <= m; ++i) {
    int a = read(), b = read(), c = read();
    if (a == 2)
      q[++tot] = {i, a, b, c, 0};
    else {
      q[++tot] = {i, a, pre[b], b, pre[b] - b};
      st[w[b]].erase(b);
      nxt[pre[b]] = nxt[b];
      if (nxt[b] != n + 1) {
        q[++tot] = {i, a, b, nxt[b], b - nxt[b]};
        q[++tot] = {i, a, pre[b], nxt[b], nxt[b] - pre[b]};
        pre[nxt[b]] = pre[b], nxt[pre[b]] = nxt[b];
      }
      st[c].insert(b);
      w[b] = c;
      pre[b] = get_pre(b), nxt[b] = get_nxt(b);
      q[++tot] = {i, a, pre[b], b, b - pre[b]};
      nxt[pre[b]] = b;
      if (nxt[b] != n + 1) {
        q[++tot] = {i, a, pre[b], nxt[b], pre[b] - nxt[b]};
        q[++tot] = {i, a, b, nxt[b], nxt[b] - b};
        pre[nxt[b]] = b;
      }
    }
  }
  cdq(1, tot);
  sort(q + 1, q + tot + 1, cmp1);
  for (int i = 1; i <= tot; ++i)
    if (q[i].opt == 2) printf("%d\n", ans[q[i].id]);
}
