#include <bits/stdc++.h>
using namespace std;
const int M = 100005;
int n, m, A[M];
set<int> S[M];
set<int>::iterator it, it2, it3;
struct BIT {
  long long sum[M];
  void clear() {
    for (int i = 1; i <= n; i++) sum[i] = 0;
  }
  void add(int x, int a) {
    while (x <= n) {
      sum[x] += a;
      x += -x & x;
    }
  }
  long long query(int x) {
    int res = 0;
    while (x > 0) {
      res += sum[x];
      x -= -x & x;
    }
    return res;
  }
} BIT;
int len, qwq;
long long ans[M];
struct Query {
  int t, x, y, ty, id;
  void rd(int ti, int xi, int yi, int tyi, int idi) {
    t = ti;
    x = xi, y = yi;
    ty = tyi;
    id = idi;
  }
  bool operator<(const Query& tmp) const {
    if (x != tmp.x) return x < tmp.x;
    return ty < tmp.ty;
  }
  void pt() { printf("t=%d x=%d y=%d ty=%d id=%d\n", t, x, y, ty, id); }
} Q[7 * M], B[7 * M];
void solve(int L, int R) {
  if (L >= R) return;
  int mid = L + R >> 1;
  solve(L, mid), solve(mid + 1, R);
  int l1 = L, l2 = mid + 1, l3 = L;
  while (l1 <= mid && l2 <= R) {
    if (Q[l1] < Q[l2]) {
      if (Q[l1].id == 0) {
        BIT.add(Q[l1].y, (Q[l1].ty - 2) * (Q[l1].x - Q[l1].y));
      }
      B[l3++] = Q[l1++];
    } else {
      if (Q[l2].id != 0) {
        ans[Q[l2].id] += (Q[l2].ty - 5) * BIT.query(Q[l2].y);
      }
      B[l3++] = Q[l2++];
    }
  }
  while (l1 <= mid) {
    if (Q[l1].id == 0) {
      BIT.add(Q[l1].y, (Q[l1].ty - 2) * (Q[l1].x - Q[l1].y));
    }
    B[l3++] = Q[l1++];
  }
  while (l2 <= R) {
    if (Q[l2].id != 0) {
      ans[Q[l2].id] += (Q[l2].ty - 5) * BIT.query(Q[l2].y);
    }
    B[l3++] = Q[l2++];
  }
  for (int i = L; i <= mid; i++) {
    if (Q[i].id == 0) {
      BIT.add(Q[i].y, -(Q[i].ty - 2) * (Q[i].x - Q[i].y));
    }
  }
  for (int i = L; i <= R; i++) {
    Q[i] = B[i];
  }
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &A[i]);
    S[A[i]].insert(i);
    it = S[A[i]].find(i);
    if (it != S[A[i]].begin()) {
      it--;
      len++;
      Q[len].rd(len, i, *it, 3, 0);
    }
  }
  int op, p, x, l, r;
  for (int i = 1; i <= m; i++) {
    scanf("%d", &op);
    if (op == 1) {
      scanf("%d %d", &p, &x);
      it3 = S[A[p]].find(p);
      it = it3;
      it3++;
      if (it != S[A[p]].begin() && it3 != S[A[p]].end()) {
        it2 = it;
        it2--;
        len++;
        Q[len].rd(len, *it, *it2, 1, 0);
        len++;
        Q[len].rd(len, *it3, *it, 1, 0);
        len++;
        Q[len].rd(len, *it3, *it2, 3, 0);
      } else if (it != S[A[p]].begin()) {
        it2 = it;
        it2--;
        len++;
        Q[len].rd(len, *it, *it2, 1, 0);
      } else if (it3 != S[A[p]].end()) {
        len++;
        Q[len].rd(len, *it3, *it, 1, 0);
      }
      S[A[p]].erase(p);
      A[p] = x;
      S[x].insert(p);
      it3 = S[x].find(p);
      it = it3;
      it3++;
      if (it != S[A[p]].begin() && it3 != S[A[p]].end()) {
        it2 = it;
        it2--;
        len++;
        Q[len].rd(len, *it3, *it2, 1, 0);
        len++;
        Q[len].rd(len, *it, *it2, 3, 0);
        len++;
        Q[len].rd(len, *it3, *it, 3, 0);
      } else if (it != S[A[p]].begin()) {
        it2 = it;
        it2--;
        len++;
        Q[len].rd(len, *it, *it2, 3, 0);
      } else if (it3 != S[A[p]].end()) {
        len++;
        Q[len].rd(len, *it3, *it, 3, 0);
      }
    } else {
      scanf("%d %d", &l, &r);
      qwq++;
      len++;
      Q[len].rd(len, l - 1, l - 1, 6, qwq);
      len++;
      Q[len].rd(len, l - 1, r, 4, qwq);
      len++;
      Q[len].rd(len, r, l - 1, 4, qwq);
      len++;
      Q[len].rd(len, r, r, 6, qwq);
    }
  }
  solve(1, len);
  for (int i = 1; i <= qwq; i++) {
    printf("%lld\n", ans[i]);
  }
  return 0;
}
