#include <bits/stdc++.h>
using namespace std;
struct cmp {
  bool operator()(int x1, int x2) { return x1 > x2; }
};
long long sum[400005];
int lson[400005], rson[400005];
int num[100005];
int root[100005], cnt = 0;
set<int, cmp> s1[100005];
set<int> s2[100005];
set<int, cmp>::iterator now1;
set<int>::iterator now2;
int build(int l, int r) {
  int x = cnt;
  cnt++;
  if (l != r) {
    lson[x] = build(l, (l + r) / 2);
    rson[x] = build((l + r) / 2 + 1, r);
  }
  return x;
}
int lowb(int x) { return -x & x; }
int add(int x, int l, int r, int p, int v) {
  int y = cnt;
  cnt++;
  sum[y] = sum[x] + v;
  if (l != r) {
    if (p <= (l + r) / 2) {
      rson[y] = rson[x];
      lson[y] = add(lson[x], l, (l + r) / 2, p, v);
    } else {
      lson[y] = lson[x];
      rson[y] = add(rson[x], (l + r) / 2 + 1, r, p, v);
    }
  }
  return y;
}
long long ask(int x, int l, int r, int p) {
  if (l == p)
    return sum[x];
  else {
    if (p <= (l + r) / 2)
      return sum[rson[x]] + ask(lson[x], l, (l + r) / 2, p);
    else
      return ask(rson[x], (l + r) / 2 + 1, r, p);
  }
}
int main() {
  int n, x, m, t, l, r;
  int f1, f2;
  long long ans;
  scanf("%d%d", &n, &m);
  root[0] = build(1, n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &num[i]);
    s1[num[i]].insert(i);
    s2[num[i]].insert(i);
    now1 = s1[num[i]].upper_bound(i);
    if (now1 != s1[num[i]].end()) {
      x = i;
      while (x <= n) {
        root[x] = add(root[x], 1, n, (*now1), i - (*now1));
        x += lowb(x);
      }
    }
  }
  while (m--) {
    scanf("%d%d%d", &t, &l, &r);
    if (t == 1) {
      f1 = 0;
      f2 = 0;
      s1[num[l]].erase(l);
      s2[num[l]].erase(l);
      now2 = s2[num[l]].upper_bound(l);
      if (now2 != s2[num[l]].end()) {
        x = (*now2);
        while (x <= n) {
          root[x] = add(root[x], 1, n, l, l - (*now2));
          x += lowb(x);
        }
      }
      now1 = s1[num[l]].upper_bound(l);
      if (now1 != s1[num[l]].end()) {
        x = l;
        while (x <= n) {
          root[x] = add(root[x], 1, n, (*now1), (*now1) - l);
          x += lowb(x);
        }
      }
      num[l] = r;
      s1[num[l]].insert(l);
      s1[num[l]].insert(l);
      now2 = s2[num[l]].upper_bound(l);
      if (now2 != s2[num[l]].end()) {
        x = (*now2);
        f2 = (*now2);
        while (x <= n) {
          root[x] = add(root[x], 1, n, l, (*now2) - l);
          x += lowb(x);
        }
      }
      now1 = s1[num[l]].upper_bound(l);
      if (now1 != s1[num[l]].end()) {
        x = l;
        f1 = (*now1);
        while (x <= n) {
          root[x] = add(root[x], 1, n, (*now1), l - (*now1));
          x += lowb(x);
        }
      }
      if (f1 && f2) {
        x = f2;
        while (x <= n) {
          root[x] = add(root[x], 1, n, f1, f1 - f2);
          x += lowb(x);
        }
      }
    } else {
      ans = 0;
      while (r) {
        ans += ask(root[r], 1, n, l);
        r -= lowb(r);
      }
      printf("%lld\n", ans);
    }
  }
  return 0;
}
