#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, f = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
  return f ? -x : x;
}
void write(long long x) {
  if (x < 0) x = -x, putchar('-');
  if (x >= 10) write(x / 10);
  putchar(x % 10 + '0');
}
inline void writeln(long long x) {
  write(x);
  puts("");
}
set<long long> g[100010];
long long a[100010], f[2010][2010], n, Q, L[100010], R[100010], bel[100010],
    mp[100010], pre[100010], nxt[100010], tot, cnt;
inline bool in(long long x, long long l, long long r) {
  return bel[x] >= l && bel[x] <= r;
}
void change(long long x, long long v, long long ref) {
  long long a = pre[x], b = nxt[x];
  bool fl, fl2, fl3;
  for (int i = 1; i <= tot; ++i)
    for (int j = i; j <= tot; ++j) {
      fl = in(a, i, j), fl2 = in(x, i, j), fl3 = in(b, i, j);
      if (fl && fl2 && !fl3) f[i][j] += ref * (x - a);
      if (fl3 && fl2 && !fl) f[i][j] += ref * (b - x);
    }
}
long long query(long long l, long long r) {
  long long x = bel[l], y = bel[r], ans = 0;
  if (x + 1 >= y) {
    for (int i = l; i <= r; ++i) {
      if (mp[a[i]]) ans += i - mp[a[i]];
      mp[a[i]] = i;
    }
    for (int i = l; i <= r; ++i) mp[a[i]] = 0;
    return ans;
  }
  ans = f[x + 1][y - 1];
  for (int i = R[x]; i >= l; --i)
    if (nxt[i] <= R[y - 1]) ans += nxt[i] - i;
  for (int i = L[y]; i <= r; ++i)
    if (pre[i] >= l) ans += i - pre[i];
  return ans;
}
int main() {
  n = read();
  Q = read();
  cnt = 2000;
  for (int i = 1; i <= n; ++i) a[i] = read(), g[a[i]].insert(i);
  for (int i = 1; i <= n; ++i) bel[i] = (i - 1) / cnt + 1;
  tot = bel[n];
  for (int i = 1; i <= tot; ++i)
    L[i] = (i - 1) * cnt + 1, R[i] = min(n, i * cnt);
  for (int i = 1; i <= n; ++i) {
    pre[i] = mp[a[i]];
    mp[a[i]] = i;
  }
  memset(mp, 0, sizeof mp);
  for (int i = n; i >= 1; --i) {
    nxt[i] = mp[a[i]];
    mp[a[i]] = i;
  }
  memset(mp, 0, sizeof mp);
  for (int i = 1; i <= tot; ++i) {
    long long ans = 0;
    for (int j = i; j <= tot; ++j) {
      for (int k = L[j]; k <= R[j]; ++k) {
        if (mp[a[k]]) ans += (k - mp[a[k]]);
        mp[a[k]] = k;
      }
      f[i][j] = ans;
    }
    memset(mp, 0, sizeof mp);
  }
  while (Q--) {
    long long opt = read(), l = read(), r = read();
    if (opt == 1) {
      change(l, a[l], -1);
      long long A = pre[l], B = nxt[l];
      nxt[A] = B;
      pre[B] = A;
      pre[0] = nxt[0] = 0;
      g[a[l]].erase(l);
      a[l] = r;
      g[r].insert(l);
      set<long long>::iterator t = g[r].lower_bound(l);
      nxt[l] = pre[l] = 0;
      ++t;
      if (t != g[r].end()) {
        pre[*t] = l;
        nxt[l] = *t;
      }
      --t;
      if (t != g[r].begin()) {
        --t;
        nxt[*t] = l;
        pre[l] = *t;
      }
      change(l, a[l], 1);
    } else
      writeln(query(l, r));
  }
}
