#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int N = 1e5 + 5, K = 2;
const int INF = 1e9 + 7;
const double alpha = 0.83;
int n, m, a[N], lst[N];
set<int> bag[N];
struct Point {
  int x[K], val;
} p[N * 7];
int cmp_data;
bool cmp(Point a, Point b) {
  if (a.x[cmp_data] != b.x[cmp_data]) return a.x[cmp_data] < b.x[cmp_data];
  return false;
}
struct KD_Tree {
  int rt, tot, top, rub[N * 7];
  struct Node {
    int ls, rs, size, sum;
    Point p;
    int div, minn[K], maxn[K];
  } tr[N * 7];
  KD_Tree() {
    for (int i = 0; i < K; ++i) tr[0].minn[i] = INF;
    for (int i = 0; i < K; ++i) tr[0].maxn[i] = -INF;
  }
  int newnode() {
    if (top) return rub[top--];
    return ++tot;
  }
  void recycle(int u) { tr[u] = tr[0], rub[++top] = u; }
  void up(int u) {
    tr[u].size = tr[tr[u].ls].size + tr[tr[u].rs].size + 1;
    tr[u].sum = tr[tr[u].ls].sum + tr[tr[u].rs].sum + tr[u].p.val;
    for (int i = 0; i < K; ++i) tr[u].minn[i] = tr[u].maxn[i] = tr[u].p.x[i];
    for (int i = 0; i < K; ++i) {
      tr[u].minn[i] = min(tr[u].minn[i], tr[tr[u].ls].minn[i]);
      tr[u].minn[i] = min(tr[u].minn[i], tr[tr[u].rs].minn[i]);
      tr[u].maxn[i] = max(tr[u].maxn[i], tr[tr[u].ls].maxn[i]);
      tr[u].maxn[i] = max(tr[u].maxn[i], tr[tr[u].rs].maxn[i]);
    }
  }
  int build(int l, int r, Point p[]) {
    if (l > r) return 0;
    int u = newnode(), mid = (l + r) >> 1;
    tr[u].div = rand() % 2, cmp_data = tr[u].div,
    nth_element(p + l, p + mid, p + r + 1, cmp), tr[u].p = p[mid];
    tr[u].ls = build(l, mid - 1, p), tr[u].rs = build(mid + 1, r, p);
    return up(u), u;
  }
  bool check(int u) {
    return alpha * tr[u].size <= max(tr[tr[u].ls].size, tr[tr[u].rs].size);
  }
  void dfs(int u, int &cnt) {
    if (!u) return;
    dfs(tr[u].ls, cnt), dfs(tr[u].rs, cnt);
    p[++cnt] = tr[u].p, recycle(u);
  }
  void rebuild(int &u) {
    int cnt = 0;
    dfs(u, cnt), u = build(1, cnt, p);
  }
  void insert(int &u, Point p) {
    if (!u) return u = newnode(), tr[u].p = p, up(u);
    if (p.x[tr[u].div] <= tr[u].p.x[tr[u].div])
      insert(tr[u].ls, p);
    else
      insert(tr[u].rs, p);
    if (check(u)) rebuild(u);
    return up(u);
  }
  int query(int u, int xl[], int xr[]) {
    if (!u) return 0;
    for (int i = 0; i < K; ++i)
      if (tr[u].minn[i] > xr[i] || tr[u].maxn[i] < xl[i]) return 0;
    int flag1 = 1, flag2 = 1;
    for (int i = 0; i < K; ++i)
      flag1 &= (xl[i] <= tr[u].minn[i] && tr[u].maxn[i] <= xr[i]);
    if (flag1) return tr[u].sum;
    for (int i = 0; i < K; ++i)
      flag2 &= (xl[i] <= tr[u].p.x[i] && tr[u].p.x[i] <= xr[i]);
    return flag2 * tr[u].p.val + query(tr[u].ls, xl, xr) +
           query(tr[u].rs, xl, xr);
  }
} t;
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    Point p;
    scanf("%d", &a[i]), bag[a[i]].insert(i);
    set<int>::iterator tmp = bag[a[i]].find(i);
    if (tmp != bag[a[i]].begin())
      p.x[1] = *tmp, tmp--, lst[i] = p.x[0] = *tmp;
    else
      p.x[1] = *tmp, lst[i] = p.x[0] = 0;
    p.val = p.x[1] - p.x[0], t.insert(t.rt, p);
  }
  for (int i = 1; i <= m; ++i) {
    int opt, x, y;
    scanf("%d%d%d", &opt, &x, &y);
    if (opt == 2) {
      int xl[K], xr[K];
      xl[0] = xl[1] = x, xr[0] = xr[1] = y;
      printf("%d\n", t.query(1, xl, xr));
    } else {
      Point p;
      set<int>::iterator tmp;
      tmp = bag[a[x]].find(x);
      if (tmp != bag[a[x]].end()) {
        p.x[0] = lst[*tmp], p.x[1] = *tmp;
        p.val = p.x[0] - p.x[1], t.insert(t.rt, p);
      }
      tmp = bag[a[x]].upper_bound(x);
      if (tmp != bag[a[x]].end()) {
        p.x[0] = lst[*tmp], p.x[1] = *tmp;
        p.val = p.x[0] - p.x[1], t.insert(t.rt, p);
      }
      tmp = bag[y].upper_bound(x);
      if (tmp != bag[y].end()) {
        p.x[0] = lst[*tmp], p.x[1] = *tmp;
        p.val = p.x[0] - p.x[1], t.insert(t.rt, p);
      }
      bag[a[x]].erase(bag[a[x]].find(x)), bag[y].insert(x);
      tmp = bag[y].find(x);
      if (tmp != bag[y].end()) {
        int fuck = *tmp;
        if (tmp != bag[y].begin())
          p.x[1] = *tmp, tmp--, lst[fuck] = p.x[0] = *tmp;
        else
          p.x[1] = *tmp, lst[fuck] = p.x[0] = 0;
        p.val = p.x[1] - p.x[0], t.insert(t.rt, p);
      }
      tmp = bag[y].upper_bound(x);
      if (tmp != bag[y].end()) {
        int fuck = *tmp;
        if (tmp != bag[y].begin())
          p.x[1] = *tmp, tmp--, lst[fuck] = p.x[0] = *tmp;
        else
          p.x[1] = *tmp, lst[fuck] = p.x[0] = 0;
        p.val = p.x[1] - p.x[0], t.insert(t.rt, p);
      }
      tmp = bag[a[x]].upper_bound(x);
      if (tmp != bag[a[x]].end()) {
        int fuck = *tmp;
        if (tmp != bag[a[x]].begin())
          p.x[1] = *tmp, tmp--, lst[fuck] = p.x[0] = *tmp;
        else
          p.x[1] = *tmp, lst[fuck] = p.x[0] = 0;
        p.val = p.x[1] - p.x[0], t.insert(t.rt, p);
      }
      a[x] = y;
    }
  }
  return 0;
}
