#include <bits/stdc++.h>
using namespace std;
const int N = 100009;
struct query {
  int a, b, op, s;
} q[N * 9], b[N * 9];
int n, m, a[N], ans[N], cnt, cntq, tr[N];
set<int> Set[N];
inline void add(int x, int c) {
  while (x <= n) {
    tr[x] += c, x += (x & -x);
  }
}
inline int ask(int x) {
  int res = 0;
  while (x) {
    res += tr[x], x -= (x & -x);
  }
  return res;
}
inline bool cmp(query x, query y) {
  if (x.op != y.op)
    return x.op < y.op;
  else if (x.op)
    return x.a < y.a;
  else
    return x.b < y.b;
}
void cdq(int l, int r) {
  if (l >= r) return;
  int mid = (l + r) >> 1;
  cdq(l, mid), cdq(mid + 1, r);
  int p1 = l, p2 = mid + 1, Cnt = l;
  for (int i = mid + 1; i <= r; i++)
    if (q[i].op) {
      while (p1 <= mid && (q[p1].b <= q[i].b)) {
        if (!q[p1].op) add(q[p1].a, (q[p1].s * (q[p1].b - q[p1].a)));
        p1++;
      }
      ans[q[i].op] += ask(n) - ask(q[i].a - 1);
    }
  for (int i = l; i < p1; i++)
    if (!q[i].op) add(q[i].a, -(q[i].s * (q[i].b - q[i].a)));
  for (int k = l, i = l, j = mid + 1; k <= r; k++)
    b[k] = (j > r || (i <= mid && q[i].b <= q[j].b)) ? q[i++] : q[j++];
  for (int i = l; i <= r; i++) q[i] = b[i];
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    Set[a[i]].insert(i);
    if (Set[a[i]].size() != 1) q[++cnt] = {*(--Set[a[i]].rbegin()), i, 0, 1};
  }
  for (int i = 1; i <= m; i++) {
    int op, b, c, l = 0, r = 0;
    scanf("%d%d%d", &op, &b, &c);
    if (op == 2) {
      q[++cnt] = {b, c, ++cntq, 0};
    } else {
      set<int>::iterator i = Set[a[b]].find(b);
      if (i != Set[a[b]].begin()) {
        l = *--i;
        q[++cnt] = {l, b, 0, -1};
        i++;
      }
      if (++i != Set[a[b]].end()) {
        r = *i;
        q[++cnt] = {b, r, 0, -1};
      }
      if (l && r) q[++cnt] = {l, r, 0, 1};
      Set[a[b]].erase(b);
      Set[c].insert(b);
      l = r = 0;
      i = Set[c].find(b);
      a[b] = c;
      if (i != Set[c].begin()) {
        l = *--i;
        q[++cnt] = {l, b, 0, 1};
        i++;
      }
      if (++i != Set[c].end()) {
        r = *i;
        q[++cnt] = {b, r, 0, 1};
      }
      if (l && r) q[++cnt] = {l, r, 0, -1};
    }
  }
  for (int i = 1; i <= cnt; i++) printf("%d %d\n", q[i].a, q[i].b);
  cdq(1, cnt);
  for (int i = 1; i <= cntq; i++) printf("%d\n", ans[i]);
  return 0;
}
