#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9')
    x = (x << 3) + (x << 1) + (c ^ '0'), c = getchar();
  return x * f;
}
const int N = 1e5 + 5;
int n, m;
struct Bit {
  long long c[N];
  inline void add(int x, int v) {
    for (; x <= N - 5; x += x & -x) c[x] += v;
  }
  inline int query(int x) {
    int res = 0;
    for (; x >= 1; x -= x & -x) res += c[x];
    return res;
  }
} T;
struct node {
  int x, y, id, f;
  inline int val() { return f > 0 ? x - y : y - x; }
} a[N << 3], w[N << 3];
long long ans[N];
void Div(int l, int r) {
  if (l >= r) return;
  int mid = (l + r) >> 1, p = l, q = mid + 1;
  Div(l, mid), Div(mid + 1, r);
  for (; q <= r; q++)
    if (a[q].id) {
      while (p <= mid && a[p].x <= a[q].x) {
        if (!a[p].id) T.add(a[p].y, a[p].val());
        p++;
      }
      ans[a[q].id] += T.query(n) - T.query(a[q].y - 1);
    }
  for (int i = l; i < p; i++)
    if (!a[i].id) T.add(a[i].y, -a[i].val());
  p = l, q = mid + 1;
  for (int i = l; i <= r; i++) {
    if ((p <= mid && a[p].x <= a[q].x) || q > r)
      w[i] = a[p++];
    else
      w[i] = a[q++];
  }
  for (int i = l; i <= r; i++) a[i] = w[i];
}
set<int> st[N];
int p[N], tot;
int main() {
  n = read(), m = read();
  for (int i = 1; i <= n; i++) {
    p[i] = read();
    st[p[i]].insert(i);
    if (st[p[i]].size() > 1) a[++tot] = {i, *(--st[p[i]].rbegin()), 0, 1};
  }
  int t = 0;
  while (m--) {
    int op = read(), l = read(), r = read();
    if (op == 2) {
      a[++tot] = {r, l, ++t, 0};
      continue;
    }
    auto i = st[p[l]].find(l);
    int L = 0, R = 0;
    if (i != st[p[l]].begin()) L = *(--i), a[++tot] = {l, L, 0, -1}, i++;
    if (++i != st[p[l]].end()) R = *i, a[++tot] = {R, l, 0, -1};
    if (L && R) a[++tot] = {R, L, 0, 1};
    st[p[l]].erase(l);
    p[l] = r;
    st[p[l]].insert(l), i = st[p[l]].find(l), L = R = 0;
    if (i != st[p[l]].begin()) L = *(--i), a[++tot] = {l, L, 0, 1}, i++;
    if (++i != st[p[l]].end()) R = *i, a[++tot] = {R, l, 0, 1};
    if (L && R) a[++tot] = {R, L, 0, -1};
  }
  Div(1, tot);
  for (int i = 1; i <= t; i++) printf("%lld\n", ans[i]);
  return 0;
}
