#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 2e6 + 5;
int n, m, a[N], cnt, num, all;
long long ans[N];
set<int> st1[N], st2[N];
set<int>::iterator it;
struct S {
  int x, y, y1, y2, f, v, id;
} s[M], t[M];
struct BIT {
  long long t[N];
  inline int lowbit(int x) { return x & -x; }
  inline void add(int x, int v) {
    while (x <= n) t[x] += v, x += lowbit(x);
  }
  inline void add(int x, int y, int v) {
    add(x, v);
    if (y < n) add(y + 1, -v);
  }
  inline long long query(int x) {
    long long tmp = 0;
    while (x) tmp += t[x], x -= lowbit(x);
    return tmp;
  }
  inline void clear(int x) {
    while (x <= n) t[x] = 0, x += lowbit(x);
  }
  inline void clear(int x, int y) {
    clear(x);
    if (y < n) clear(y + 1);
  }
} tt;
inline void add(int x, int y, int y1, int y2, int f, int v, int id) {
  if (x >= 1 && x <= n && y1 >= 1 && y1 <= n && y2 >= 1 && y2 <= n && y1 <= y2)
    s[++cnt] = (S){x, y, y1, y2, f, v, id};
}
inline void add2(int x, int y, int y1, int y2, int f, int v, int id) {
  s[++cnt] = (S){x, y, y1, y2, f, v, id};
}
inline bool cmp(S a, S b) {
  if (a.x != b.x) return a.x < b.x;
  return a.f > b.f;
}
inline void solve(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  solve(l, mid);
  all = 0;
  for (int i = l; i <= mid; i++)
    if (s[i].f == -1 || s[i].f == 1) t[++all] = s[i];
  for (int i = mid + 1; i <= r; i++)
    if (s[i].f == 0) t[++all] = s[i];
  sort(t + 1, t + all + 1, cmp);
  for (int i = 1; i <= all; i++) {
    if (t[i].f == 1) tt.add(t[i].y1, t[i].y2, t[i].v);
    if (t[i].f == -1) tt.add(t[i].y1, t[i].y2, -t[i].v);
    if (t[i].f == 0) ans[t[i].id] += tt.query(t[i].y);
  }
  for (int i = 1; i <= all; i++) {
    if (t[i].f == 1) tt.clear(t[i].y1, t[i].y2);
    if (t[i].f == -1) tt.clear(t[i].y1, t[i].y2);
  }
  solve(mid + 1, r);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) {
    int L = 0, R = n + 1, M = i;
    it = st1[a[M]].upper_bound(-M);
    if (it != st1[a[M]].end()) L = -(*it);
    it = st2[a[M]].upper_bound(M);
    if (it != st2[a[M]].end()) R = (*it);
    if (R != n + 1) add(L + 1, 0, R, n, 1, R - M, 0);
    if (R != n + 1) add(M, 0, R, n, -1, R - M, 0);
    if (L != 0) add(1, 0, M, R - 1, 1, M - L, 0);
    if (L != 0) add(L, 0, M, R - 1, -1, M - L, 0);
    st1[a[i]].insert(-i), st2[a[i]].insert(i);
  }
  while (m--) {
    int t, x, y;
    scanf("%d%d%d", &t, &x, &y);
    if (t == 1) {
      int L = 0, R = n + 1, M = x;
      it = st1[a[M]].upper_bound(-M);
      if (it != st1[a[M]].end()) L = -(*it);
      it = st2[a[M]].upper_bound(M);
      if (it != st2[a[M]].end()) R = (*it);
      if (R != n + 1) add(L + 1, 0, R, n, 1, -(R - M), 0);
      if (R != n + 1) add(M, 0, R, n, -1, -(R - M), 0);
      if (L != 0) add(1, 0, M, R - 1, 1, -(M - L), 0);
      if (L != 0) add(L, 0, M, R - 1, -1, -(M - L), 0);
      st1[a[M]].erase(-M);
      st2[a[M]].erase(M);
      a[M] = y;
      st1[a[M]].insert(-M);
      st2[a[M]].insert(M);
      L = 0, R = n + 1, M = x;
      it = st1[a[M]].upper_bound(-M);
      if (it != st1[a[M]].end()) L = -(*it);
      it = st2[a[M]].upper_bound(M);
      if (it != st2[a[M]].end()) R = (*it);
      if (R != n + 1) add(L + 1, 0, R, n, 1, R - M, 0);
      if (R != n + 1) add(M, 0, R, n, -1, R - M, 0);
      if (L != 0) add(1, 0, M, R - 1, 1, M - L, 0);
      if (L != 0) add(L, 0, M, R - 1, -1, M - L, 0);
    }
    if (t == 2) add2(x, y, 0, 0, 0, 0, ++num);
  }
  solve(1, cnt);
  for (int i = 1; i <= num; i++) printf("%I64d\n", ans[i]);
  return 0;
}
