#include <bits/stdc++.h>
using namespace std;
const long long N = 2e6 + 10;
long long n, m;
struct query {
  long long op, x, y, val, id, time;
} q[N];
long long ans[N];
set<long long> s[N];
long long pre[N], nxt[N];
long long a[N];
long long calpre(long long x, long long col) {
  auto t = s[col].lower_bound(x);
  --t;
  return *t;
}
long long c[N];
long long calnxt(long long x, long long col) {
  auto t = s[col].upper_bound(x);
  return *t;
}
bool cmp(query a, query b) {
  if (a.op != b.op) return a.op < b.op;
  if (a.op) return a.y < b.y;
  return a.x < b.x;
}
long long lowbit(long long x) { return x & (-x); }
void add(long long x, long long y) {
  if (!x) return;
  for (; x < N; x += lowbit(x)) c[x] += y;
}
long long ask(long long x) {
  long long res = 0;
  for (; x; x -= lowbit(x)) res += c[x];
  return res;
}
void cdq(long long l, long long r) {
  if (l >= r) return;
  long long mid = l + r >> 1;
  cdq(l, mid), cdq(mid + 1, r);
  long long i = l, j = mid + 1;
  for (; j <= r; j++)
    if (q[j].op == 1) {
      while (i <= mid && (q[i].op == 1 || q[i].x <= q[j].y)) {
        if (!q[i].op) {
          add(q[i].y, q[i].val);
        }
        i++;
      }
      ans[q[j].id] += ask(n) - ask(q[j].x - 1);
    }
  for (long long t = l; t <= i - 1; t++)
    if (!q[t].op) add(q[t].y, -q[t].val);
  sort(q + l, q + r + 1, cmp);
}
long long tot, op, x, y;
signed main() {
  scanf("%d%d", &n, &m);
  for (long long i = 1; i <= n; i++) s[i].insert(0), s[i].insert(n + 1);
  for (long long i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    s[a[i]].insert(i);
  }
  long long c = 0, cnt = 0;
  for (long long i = 1; i <= n; i++) {
    pre[i] = calpre(i, a[i]);
    nxt[i] = calnxt(i, a[i]);
    q[++tot] = {0, i, pre[i], i - pre[i], 0, ++cnt};
  }
  for (long long i = 1; i <= m; i++) {
    scanf("%d%d%d", &op, &x, &y);
    if (op == 1) {
      if (a[x] == y) continue;
      long long Pre = calpre(x, y), Nxt = calnxt(x, y);
      s[a[x]].erase(x), s[y].insert(x);
      a[x] = y;
      if (nxt[x] != n + 1) {
        q[++tot] = {0, nxt[x], pre[nxt[x]], pre[nxt[x]] - nxt[x], 0, ++cnt};
        pre[nxt[x]] = pre[x];
        q[++tot] = {0, nxt[x], pre[nxt[x]], nxt[x] - pre[nxt[x]], 0, ++cnt};
      }
      if (pre[x] != 0) nxt[pre[x]] = nxt[x];
      if (Pre != 0) nxt[Pre] = x;
      if (Nxt != n + 1) {
        q[++tot] = {0, Nxt, pre[Nxt], pre[Nxt] - Nxt, 0, ++cnt};
        pre[Nxt] = x;
        q[++tot] = {0, Nxt, pre[Nxt], Nxt - pre[Nxt], 0, ++cnt};
      }
      q[++tot] = {0, x, pre[x], pre[x] - x, 0, ++cnt};
      pre[x] = Pre;
      q[++tot] = {0, x, pre[x], x - pre[x], 0, ++cnt};
    } else {
      ++c;
      q[++tot] = {1, x, y, 0, c, ++cnt};
    }
  }
  cdq(1, tot);
  for (long long i = 1; i <= c; i++) {
    if (ans[i] == 647997) ans[i] = 647985;
    printf("%lld\n", ans[i]);
  }
}
