#include <bits/stdc++.h>
using namespace std;
inline void read(int &x) {
  char ch;
  while ((ch = getchar()), (ch < '0' || ch > '9'))
    ;
  x = ch - '0';
  while ((ch = getchar()), (ch >= '0' && ch <= '9')) x = x * 10 + (ch - '0');
}
const int MAXN = 100010;
int N, Q, Len = 0;
struct item {
  int x, y, v;
  char op;
  inline bool operator<(item rhs) const {
    return (x == rhs.x) ? (op < rhs.op) : (x < rhs.x);
  }
} A[7 * MAXN], T[7 * MAXN];
long long Ans[MAXN];
int LenAns = 0;
namespace BIT {
long long C[MAXN];
inline void add(int id, int x) {
  while (id <= N) {
    C[id] += x;
    id += ((id) & -(id));
  }
}
inline void clear(int id) {
  while (id <= N) {
    C[id] = 0;
    id += ((id) & -(id));
  }
}
inline long long sum(int id) {
  long long ans = 0;
  while (id) {
    ans += C[id];
    id -= ((id) & -(id));
  }
  return ans;
}
}  // namespace BIT
void divide(int L, int R) {
  if (R - L > 1) {
    int M = (L + R) >> 1;
    divide(L, M);
    divide(M, R);
    int i, pl = L, pr = M, c = 0;
    while ((pl < M) || (pr < R)) {
      if (!(pl < M) || ((pr < R) && (A[pr] < A[pl]))) {
        if (A[pr].op == 1)
          Ans[A[pr].v] += BIT::sum(A[pr].y);
        else if (A[pr].op == 2)
          Ans[A[pr].v] -= BIT::sum(A[pr].y);
        T[c++] = A[pr++];
      } else {
        if (A[pl].op == 0) BIT::add(A[pl].y, A[pl].v);
        T[c++] = A[pl++];
      }
    }
    for (i = L; i < M; i++)
      if (A[i].op == 0) BIT::clear(A[i].y);
    for (i = L; i < R; i++) A[i] = T[i - L];
  }
}
inline void addrect(int xl, int xr, int yl, int yr, int id) {
  A[Len++] = {xr, yr, id, 1};
  A[Len++] = {xr, yl - 1, id, 2};
  A[Len++] = {xl - 1, yr, id, 2};
  A[Len++] = {xl - 1, yl - 1, id, 1};
}
set<int> S[MAXN];
set<int>::iterator it, oit;
int V[MAXN];
int main() {
  int i, op, l, r, t, p, x;
  read(N);
  read(Q);
  for (i = 1; i <= N; i++) {
    read(V[i]);
    it = S[V[i]].insert(i).first;
    if (it != S[V[i]].begin()) t = *(--it), A[Len++] = {i, t, i - t, 0};
  }
  while (Q--) {
    read(op);
    if (op == 1) {
      read(p);
      read(x);
      oit = S[V[p]].find(p);
      it = oit;
      t = (it == S[V[p]].begin()) ? 0 : *(--it);
      it = oit;
      it++;
      i = (it != S[V[p]].end()) ? *it : 0;
      S[V[p]].erase(oit);
      if (t) A[Len++] = {p, t, -(p - t), 0};
      if (i) {
        A[Len++] = {i, p, -(i - p), 0};
        if (t) A[Len++] = {i, t, i - t, 0};
      }
      V[p] = x;
      oit = S[V[p]].insert(p).first;
      it = oit;
      t = (it == S[V[p]].begin()) ? 0 : *(--it);
      it = oit;
      it++;
      i = (it != S[V[p]].end()) ? *it : 0;
      if (t) A[Len++] = {p, t, p - t, 0};
      if (i) {
        if (t) A[Len++] = {i, t, -(i - t), 0};
        A[Len++] = {i, p, i - p, 0};
      }
    } else {
      read(l);
      read(r);
      addrect(l, r, l, r, ++LenAns);
    }
  }
  divide(0, Len);
  for (i = 1; i <= LenAns; i++) printf("%I64d\n", Ans[i]);
}
