#include <bits/stdc++.h>
using namespace std;
int pre[100010], nxt[100010];
long long ans[55][55];
map<int, int> mp[100010];
int a[100010], bel[100010], L[55], R[55];
int cnt, n, m;
void add(int x, int y, int f) {
  for (int i = 1; i <= bel[x]; i++)
    for (int j = bel[y]; j <= cnt; j++) ans[i][j] += (long long)f * (y - x);
}
void change(int p, int x) {
  add(pre[p], p, -1);
  add(p, nxt[p], -1);
  nxt[pre[p]] = nxt[p];
  pre[nxt[p]] = pre[p];
  add(pre[p], nxt[p], 1);
  mp[a[p]].erase(p);
  map<int, int>::iterator it = mp[x].lower_bound(p);
  int p2 = it->first, p1 = (--it)->first;
  add(p1, p2, -1);
  pre[p] = p1;
  nxt[p] = p2;
  pre[p2] = p;
  nxt[p1] = p;
  add(p1, p, 1);
  add(p, p2, 1);
  mp[a[p] = x][p] = 1;
}
long long query(int l, int r) {
  int LL = bel[l], RR = bel[r];
  long long t = 0;
  if (LL + 1 <= RR - 1)
    t = ans[LL + 1][RR - 1];
  else
    t = 0;
  if (LL == RR) {
    for (int i = l; i < r; i++)
      if (nxt[i] <= r) t += nxt[i] - i;
  } else {
    for (int i = l; i <= R[LL]; i++)
      if (nxt[i] < L[RR]) t += nxt[i] - i;
    for (int i = L[RR]; i <= r; i++)
      if (pre[i] >= l) t += i - pre[i];
  }
  return t;
}
int main() {
  scanf("%d%d", &n, &m);
  bel[0] = 1;
  for (int i = 1; i <= n; i++) cnt = bel[i] = (i - 1) / 2000 + 2;
  bel[n + 1] = ++cnt;
  for (int i = 2; i < cnt; i++) L[i] = (R[i] = (i - 1) * 2000) - 2000 + 1;
  R[cnt - 1] = n;
  L[1] = R[1] = 0;
  L[cnt] = R[cnt] = n + 1;
  pre[nxt[0] = n + 1] = 0;
  for (int i = 0; i <= n; i++) pre[i] = nxt[i] = i;
  for (int i = 0; i <= n; i++) {
    mp[i].clear();
    mp[i][0] = 1;
    mp[i][n + 1] = 1;
    add(0, n + 1, 1);
  }
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    change(i, x);
  }
  while (m--) {
    int t, x, y;
    scanf("%d%d%d", &t, &x, &y);
    if (t == 1)
      change(x, y);
    else
      printf("%I64d\n", query(x, y));
  }
  return 0;
}
