#include <bits/stdc++.h>
using namespace std;
char buf[100000], *p1 = buf, *p2 = buf;
inline int gi() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
  }
  return (f == 1) ? x : -x;
}
const int maxn = 7e5 + 5;
int n, m, a[maxn];
struct queries {
  int t, typ, l, r, val;
  inline bool operator<(const queries &b) const {
    if (l == b.l)
      return typ < b.typ;
    else
      return l > b.l;
  }
} q[maxn], temp[maxn];
int tot;
set<int> s[maxn];
int pre[maxn], ans[maxn];
bool vis[maxn];
inline void init() {}
inline void input() {
  n = gi(), m = gi();
  for (int i = 1; i <= n; ++i) a[i] = gi(), s[a[i]].insert(i);
  for (int i = 1; i <= n; ++i) s[i].insert(0);
  for (int i = 1; i <= n; ++i) {
    pre[i] = *(--s[a[i]].lower_bound(i));
    q[++tot] = {0, 1, pre[i], i, i - pre[i]};
  }
  for (int i = 1; i <= m; ++i) {
    int typ = gi();
    if (typ == 1) {
      int x = gi(), c = gi();
      q[++tot] = {i, 1, pre[x], x, pre[x] - x};
      auto it = s[a[x]].upper_bound(x);
      if (it != s[a[x]].end()) {
        int y = *it;
        q[++tot] = {i, 1, x, y, x - y};
        q[++tot] = {i, 1, pre[x], y, y - pre[x]};
        pre[y] = pre[x];
      }
      s[a[x]].erase(x);
      a[x] = c;
      it = s[a[x]].upper_bound(x);
      if (it != s[a[x]].end()) {
        int y = *it;
        q[++tot] = {i, 1, pre[y], y, pre[y] - y};
        q[++tot] = {i, 1, x, y, y - x};
        pre[y] = x;
      }
      s[a[x]].insert(x);
      pre[x] = *(--s[a[x]].lower_bound(x));
      q[++tot] = {i, 1, pre[x], x, x - pre[x]};
    } else {
      int l = gi(), r = gi();
      q[++tot] = {i, 2, l, r, 0};
      vis[i] = 1;
    }
  }
}
int c[maxn];
inline void update(int x, int v) {
  while (x <= n) c[x] += v, x += x & -x;
}
inline int query(int x) {
  int ret = 0;
  while (x) ret += c[x], x -= x & -x;
  return ret;
}
inline void cdq(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  cdq(l, mid);
  cdq(mid + 1, r);
  int cnt = l - 1;
  int pos1 = l, pos2 = mid + 1;
  while (pos1 <= mid && pos2 <= r) {
    if (q[pos1] < q[pos2]) {
      if (q[pos1].typ == 1) update(q[pos1].r, q[pos1].val);
      temp[++cnt] = q[pos1++];
    } else {
      if (q[pos2].typ == 2)
        ans[q[pos2].t] += query(q[pos2].r) - query(q[pos2].l - 1);
      temp[++cnt] = q[pos2++];
    }
  }
  while (pos1 <= mid) {
    if (q[pos1].typ == 1) update(q[pos1].r, q[pos1].val);
    temp[++cnt] = q[pos1++];
  }
  while (pos2 <= r) {
    if (q[pos2].typ == 2)
      ans[q[pos2].t] += query(q[pos2].r) - query(q[pos2].l - 1);
    temp[++cnt] = q[pos2++];
  }
  for (int i = l; i <= mid; ++i) {
    if (q[i].typ == 1) update(q[i].r, -q[i].val);
  }
  for (int i = l; i <= r; ++i) q[i] = temp[i];
}
inline void solve() {
  cdq(1, tot);
  for (int i = 1; i <= m; ++i)
    if (vis[i]) printf("%d\n", ans[i]);
}
int main() {
  init();
  input();
  solve();
  return 0;
}
