#include <bits/stdc++.h>
using namespace std;
set<int> s[100010];
set<int>::iterator it;
struct Node {
  int p, x, w, f;
  Node(int p = 0, int x = 0, int w = 0, int f = 0) : p(p), x(x), w(w), f(f) {}
} b[100010 * 10], t[100010 * 10];
long long Ans[100010], c[100010], tt, v[100010];
bool f[100010];
int i, j, k, n, m, q, p, a[100010];
int x, y;
int l[100010], pr[100010], nx[100010];
inline void Modify(int x, int y) {
  if (a[x] == y) return;
  it = s[a[x]].find(x);
  int p = 0;
  if (it != s[a[x]].begin()) {
    it--;
    p = (*it);
    it++;
    b[++m] = Node(x, p, p - x);
  }
  it++;
  if (it != s[a[x]].end()) {
    b[++m] = Node(*it, x, x - (*it));
    if (p) b[++m] = Node(*it, p, (*it) - p);
  }
  s[a[x]].erase(x);
  a[x] = y;
  it = s[y].insert(x).first;
  p = 0;
  if (it != s[y].begin()) {
    it--;
    p = (*it);
    it++;
    b[++m] = Node(x, p, x - p);
  }
  it++;
  if (it != s[y].end()) {
    if (p) b[++m] = Node(*it, p, p - (*it));
    b[++m] = Node(*it, x, (*it) - x);
  }
}
inline void Update(int x, int y) {
  for (; x <= n; x += x & -x)
    if (v[x] != tt)
      v[x] = tt, c[x] = y;
    else
      c[x] += y;
}
inline long long Query(int x) {
  long long Ans = 0;
  for (; x; x -= x & -x)
    if (v[x] != tt)
      v[x] = tt, c[x] = 0;
    else
      Ans += c[x];
  return Ans;
}
inline void Solve(int l, int r) {
  if (l == r) return;
  int Mid = l + r >> 1;
  Solve(l, Mid);
  Solve(Mid + 1, r);
  int p1 = l, p2 = Mid + 1;
  ++tt;
  for (int i = l; i <= r; i++)
    if (p2 > r || (p1 <= Mid && b[p1].p <= b[p2].p)) {
      t[i] = b[p1++];
      if (!t[i].f) Update(n - t[i].x + 1, t[i].w);
    } else {
      t[i] = b[p2++];
      if (t[i].f) Ans[t[i].f] += Query(n - t[i].x + 1);
    }
  for (int i = l; i <= r; i++) b[i] = t[i];
}
int main() {
  scanf("%d%d", &n, &q);
  for (i = 1; i <= n; i++) scanf("%d", &a[i]), s[a[i]].insert(i);
  for (i = 1; i <= n; i++) {
    it = s[a[i]].find(i);
    if (it != s[a[i]].begin()) {
      it--;
      b[++m] = Node(i, *it, i - (*it));
    }
  }
  for (i = 1; i <= q; i++) {
    scanf("%d%d%d", &k, &x, &y);
    if (k == 1)
      Modify(x, y);
    else
      f[i] = 1, b[++m] = Node(y, x, 0, i);
  }
  Solve(1, m);
  for (i = 1; i <= q; i++)
    if (f[i]) printf("%I64d\n", Ans[i]);
  return 0;
}
