#include <bits/stdc++.h>
using namespace std;
const int bsize = 318;
const int maxn = 1e5 + 88;
long long sum[bsize][maxn];
int a[maxn], b[maxn], nxt[maxn], prv[maxn], cur[maxn];
int n;
int readint() {
  int cur;
  scanf("%d", &cur);
  return cur;
}
void resort(int block) {
  for (int i = block * bsize; i < min((block + 1) * bsize, n); i++) b[i] = a[i];
  sort(b + block * bsize, b + min((block + 1) * bsize, n));
}
long long getsum(int b, int pos) {
  long long ans = 0;
  for (int i = pos; i >= 0; i = (i & (i + 1)) - 1) ans += sum[b][i];
  return ans;
}
void add(int b, int pos, int d) {
  for (int i = pos; i < n; i |= (i + 1)) sum[b][i] += d;
}
int find_up(int x, int l, int r) {
  for (int i = r - 1; i >= l; i--)
    if (a[i] == x) return i;
  return -1;
}
int find_down(int x, int l, int r) {
  for (int i = l; i < r; i++)
    if (a[i] == x) return i;
  return -1;
}
long long brut(int l, int r, int g) {
  long long ans = 0;
  for (int i = l; i < r; i++)
    if (nxt[i] != -1 && nxt[i] < g) ans += nxt[i] - i;
  return ans;
}
bool check(int block, int x) {
  return binary_search(b + block * bsize, b + min((block + 1) * bsize, n), x);
}
void build() {
  int i;
  for (i = 0; i < n; i++) cur[i] = -1;
  for (i = 0; i < n; i++) {
    prv[i] = cur[a[i]];
    if (prv[i] != -1) nxt[prv[i]] = i;
    nxt[i] = -1;
    cur[a[i]] = i;
  }
  for (i = 0; i < n; i++)
    if (nxt[i] != -1) add(i / bsize, nxt[i], nxt[i] - i);
  for (i = 0; i * bsize < n; i++) resort(i);
}
void change(int pos, int x) {
  int i;
  int block = pos / bsize;
  if (nxt[pos] != -1) add(block, nxt[pos], pos - nxt[pos]);
  int curnext = nxt[pos], curprev = prv[pos];
  if (nxt[pos] != -1) prv[nxt[pos]] = prv[pos];
  if (prv[pos] != -1) nxt[prv[pos]] = nxt[pos];
  prv[pos] = find_up(x, block * bsize, pos);
  nxt[pos] = find_down(x, pos + 1, min((block + 1) * bsize, n));
  for (i = block - 1; prv[pos] == -1 && i >= 0; i--)
    if (check(i, x)) {
      prv[pos] = find_up(x, i * bsize, min((i + 1) * bsize, n));
      break;
    }
  for (i = block + 1; nxt[pos] == -1 && i < n; i++)
    if (check(i, x)) {
      nxt[pos] = find_down(x, i * bsize, min((i + 1) * bsize, n));
      break;
    }
  a[pos] = x;
  if (prv[pos] != -1) nxt[prv[pos]] = pos;
  if (nxt[pos] != -1) prv[nxt[pos]] = pos;
  resort(block);
}
long long get(int l, int r) {
  int i;
  long long ans = 0;
  int lblock = l / bsize, rblock = r / bsize;
  if (lblock == rblock) return brut(l, r + 1, r + 1);
  ans += brut(l, min((lblock + 1) * bsize, n), r + 1);
  ans += brut(rblock * bsize, r + 1, r + 1);
  for (i = lblock + 1; i < rblock; i++) ans += getsum(i, r);
  return ans;
}
int main() {
  n = readint();
  int m = readint(), i;
  for (i = 0; i < n; i++) a[i] = readint(), a[i]--;
  build();
  while (m--) {
    int t = readint(), l = readint(), r = readint();
    l--, r--;
    if (t == 1)
      change(l, r);
    else
      printf("%I64d\n", get(l, r));
  }
  return 0;
}
