#include <bits/stdc++.h>
using namespace std;
bool st;
int n, m, i, j, k, w, aim, val, opt, ll, rr, u, v;
int A_[100005], B[100005], C[100005];
int a[200005], l[200005], r[200005];
long long ans, Ans[100005], sum[100005];
bool use[100005];
vector<int> Vx[100005], Vy[100005], Vval[100005];
set<int> S[100005];
struct node {
  int opt, x, y, z;
} t[4000005];
int tot;
inline bool cmp(const node &a, const node &b) {
  if (a.x != b.x) return a.x < b.x;
  return a.opt < b.opt;
}
bool en;
void Ins(int i, int op) {
  if (r[i] > n || i == 0) return;
  Vx[w].push_back(i);
  Vy[w].push_back(r[i]);
  Vval[w].push_back((r[i] - i) * op);
}
void CDQ(int l, int r) {
  if (l == r) return;
  int mid = l + r >> 1;
  CDQ(l, mid);
  CDQ(mid + 1, r);
  tot = 0;
  for (i = l; i <= mid; ++i)
    for (j = 0; j < Vx[i].size(); ++j) {
      ++tot;
      t[tot].x = Vx[i][j];
      t[tot].y = Vy[i][j];
      t[tot].z = Vval[i][j];
      t[tot].opt = 1;
    }
  for (i = mid + 1; i <= r; ++i)
    if (A_[i] == 2) {
      ++tot;
      t[tot].x = B[i];
      t[tot].y = C[i];
      t[tot].z = i;
      t[tot].opt = 0;
      ++tot;
      t[tot].x = C[i];
      t[tot].y = C[i];
      t[tot].z = i;
      t[tot].opt = 2;
    }
  sort(t + 1, t + tot + 1, cmp);
  for (i = 1; i <= tot; ++i) {
    if (t[i].opt == 0) {
      k = t[i].z;
      for (j = t[i].y; j; j -= j & -j) Ans[k] -= sum[j];
    }
    if (t[i].opt == 1) {
      k = t[i].z;
      for (j = t[i].y; j <= n; j += j & -j) sum[j] += k;
    }
    if (t[i].opt == 2) {
      k = t[i].z;
      for (j = t[i].y; j; j -= j & -j) Ans[k] += sum[j];
    }
  }
  for (i = 1; i <= tot; ++i) {
    if (t[i].opt == 1) {
      k = t[i].z;
      for (j = t[i].y; j <= n; j += j & -j) sum[j] = 0;
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (i = 1; i <= n; ++i) S[i].insert(n + i);
  for (i = 1; i <= n; ++i) S[a[i]].insert(i);
  for (i = 1; i <= n; ++i) {
    k = *S[a[i]].lower_bound(i + 1);
    r[i] = k;
    l[k] = i;
  }
  for (i = 1; i <= m; ++i) {
    scanf("%d%d%d", &A_[i], &B[i], &C[i]);
    if (A_[i] == 2) {
      for (j = B[i] - 1; j; j -= j & -j) use[j] = true;
      for (j = C[i]; j; j -= j & -j) use[j] = true;
    }
  }
  w = 0;
  for (i = 1; i <= n; ++i) Ins(i, 1);
  for (w = 1; w <= m; ++w) {
    opt = A_[w];
    u = B[w];
    v = C[w];
    if (opt == 1) {
      Ins(u, -1);
      if (l[u] != 0) {
        Ins(l[u], -1);
        r[l[u]] = r[u];
        Ins(l[u], 1);
      }
      l[r[u]] = l[u];
      S[a[u]].erase(u);
      a[u] = v;
      S[a[u]].insert(u);
      k = *S[a[u]].lower_bound(u + 1);
      if (l[k] != 0) {
        Ins(l[k], -1);
        r[l[k]] = u;
        Ins(l[k], 1);
      }
      l[u] = l[k];
      l[k] = u;
      r[u] = k;
      Ins(u, 1);
    }
  }
  CDQ(0, m);
  for (i = 1; i <= m; ++i)
    if (A_[i] == 2) printf("%I64d\n", Ans[i]);
}
