#include <bits/stdc++.h>
using namespace std;
struct node {
  int p, x, w, type;
  node(int pp = 0, int xx = 0, int ww = 0, int ttype = 0) {
    p = pp;
    x = xx;
    w = ww;
    type = ttype;
  }
} b[1000010], c[1000010];
set<int> s[100010];
int a[100010];
int n, m;
int cnt = 0;
void gx(int x, int y) {
  if (a[x] == y) return;
  auto z = s[a[x]].find(x);
  int temp = 0;
  if (z != s[a[x]].begin()) {
    z--;
    temp = (*z);
    z++;
    b[++cnt] = node{x, temp, temp - x, 0};
  }
  z++;
  if (z != s[a[x]].end()) {
    b[++cnt] = node{*z, x, x - (*z), 0};
    if (temp != 0) b[++cnt] = node{*z, temp, (*z) - temp, 0};
  }
  s[a[x]].erase(x);
  s[y].insert(x);
  a[x] = y;
  z = s[y].find(x);
  temp = 0;
  if (z != s[y].begin()) {
    z--;
    temp = (*z);
    z++;
    b[++cnt] = node{x, temp, x - temp, 0};
  }
  z++;
  if (z != s[y].end()) {
    if (temp != 0) b[++cnt] = node{*z, temp, temp - (*z), 0};
    b[++cnt] = node{*z, x, (*z) - x, 0};
  }
}
int ans[100010];
int res[100010];
int getsum(int x) {
  int res1 = 0;
  for (int i = x; i > 0; i = i - (i & (-i))) {
    res1 += ans[i];
  }
  return res1;
}
void update(int x, int y) {
  for (int i = x; i <= n; i = i + (i & (-i))) {
    ans[i] += y;
  }
}
void cdq(int l, int r) {
  if (l == r) return;
  int mid = (l + r) / 2;
  cdq(l, mid);
  cdq(mid + 1, r);
  int t1 = l, t2 = mid + 1;
  for (int i = l; i <= r; i++) {
    if ((t1 <= mid && b[t1].p <= b[t2].p) || (t2 > r)) {
      if (b[t1].type == 0) {
        update(n - b[t1].x + 1, b[t1].w);
      }
      c[i] = b[t1++];
    } else {
      if (b[t2].type != 0) {
        res[b[t2].type] += getsum(n - b[t2].x + 1);
      }
      c[i] = b[t2++];
    }
  }
  for (int i = l; i <= mid; i++) {
    if (b[i].type == 0) {
      update(n - b[i].x + 1, -b[i].w);
    }
  }
  for (int i = l; i <= r; i++) {
    b[i] = c[i];
  }
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    s[a[i]].insert(i);
  }
  for (int i = 1; i <= n; i++) {
    auto z = s[a[i]].find(i);
    if (z != s[a[i]].begin()) {
      z--;
      b[++cnt] = node{i, *z, i - (*z), 0};
    }
  }
  int cnt1 = 0;
  for (int i = 1; i <= m; i++) {
    int x, y, z;
    scanf("%d %d %d", &z, &x, &y);
    if (z == 1) {
      gx(x, y);
    } else {
      cnt1++;
      b[++cnt] = node{y, x, 0, cnt1};
    }
  }
  cdq(1, cnt);
  for (int i = 1; i <= cnt1; i++) {
    printf("%d\n", res[i]);
  }
}
