#include <bits/stdc++.h>
using namespace std;
namespace IO {
const int IOsize = 1 << 21;
void read(){};
void Write(){};
char buf[IOsize], *pa = buf, *pb = buf;
char buffer[IOsize];
int p1 = -1;
const int p2 = (IOsize)-1;
inline char gc() {
  return pa == pb && (pb = (pa = buf) + fread(buf, 1, IOsize, stdin), pa == pb)
             ? EOF
             : *pa++;
}
template <typename T, typename... T2>
void read(T &x, T2 &...oth) {
  x = 0;
  short y = 0;
  char ch = gc();
  for (; !isdigit(ch); ch = gc()) y = ch == '-';
  for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
  (y) && (x = -x);
  read(oth...);
  return;
}
template <typename T>
inline T Read() {
  T x;
  read(x);
  return x;
}
inline void flush() {
  fwrite(buffer, 1, p1 + 1, stdout);
  p1 = -1;
  return;
}
inline void pc(int ch) {
  if (p1 == p2) flush();
  buffer[++p1] = ch;
  return;
}
template <class T>
inline void write(T x) {
  static char buf[20];
  static short len = -1;
  if (x >= 0) {
    do buf[++len] = (x % 10) ^ 48, x /= 10;
    while (x);
  } else {
    pc('-');
    do buf[++len] = (-(x % 10)) ^ 48, x /= 10;
    while (x);
  }
  while (len >= 0) pc(buf[len--]);
  return;
}
template <typename T>
void write(T x, char ch) {
  write(x), pc(ch);
}
template <typename T, typename... T2>
void Write(T x, T2... oth) {
  write(x), pc('\n'), Write(oth...);
  return;
}
}  // namespace IO
using namespace IO;
namespace work {
const int arriz = 1.1e5;
int n, m, a[arriz];
set<int> s[arriz];
namespace Bit_Seg {
int rt[arriz], ls[arriz << 6], rs[arriz << 6], sum[arriz << 6], cnt;
void modify(int pos, int val, int &o, int l = 1, int r = n) {
  if (!o) o = ++cnt;
  sum[o] += val;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (pos <= mid)
    modify(pos, val, ls[o], l, mid);
  else
    modify(pos, val, rs[o], mid + 1, r);
}
int query(int pos, int o, int l = 1, int r = n) {
  if (!o) return 0;
  if (l == r) return sum[o];
  int mid = (l + r) >> 1;
  if (pos <= mid)
    return query(pos, ls[o], l, mid);
  else
    return sum[ls[o]] + query(pos, rs[o], mid + 1, r);
}
inline int lowbit(int pos) { return pos & (-pos); }
inline void Modify(int pre, int i, int val) {
  for (int pos = pre; pos; pos -= lowbit(pos)) modify(i, val, rt[pos]);
}
inline int Query(int pre, int i) {
  int ans = 0;
  for (int pos = pre; pos <= n; pos += lowbit(pos)) ans += query(i, rt[pos]);
  return ans;
}
}  // namespace Bit_Seg
using Bit_Seg::Modify;
using Bit_Seg::Query;
signed main() {
  read(n, m);
  for (int i = 1; i <= n; ++i) read(a[i]);
  int pre;
  for (int i = 1; i <= n; ++i) {
    s[a[i]].insert(i);
    auto res = s[a[i]].lower_bound(i);
    pre = (res == s[a[i]].begin()) ? 0 : (*--res);
    if (pre) Modify(pre, i, i - pre);
  }
  int suf, opt, pos, val;
  for (int i = 1; i <= m; ++i) {
    read(opt, pos, val);
    if (opt == 2) {
      Write(Query(pos, val));
      continue;
    }
    auto res = s[a[pos]].lower_bound(pos);
    pre = (res == s[a[pos]].begin()) ? 0 : (*--res);
    auto ges = s[a[pos]].upper_bound(pos);
    suf = (ges == s[a[pos]].end()) ? 0 : (*ges);
    if (pre) Modify(pre, pos, pre - pos);
    if (suf) Modify(pos, suf, pos - suf);
    if (pre && suf) Modify(pre, suf, suf - pre);
    s[a[pos]].erase(pos);
    a[pos] = val;
    s[a[pos]].insert(pos);
    res = s[a[pos]].lower_bound(pos);
    pre = (res == s[a[pos]].begin()) ? 0 : (*--res);
    ges = s[a[pos]].upper_bound(pos);
    suf = (ges == s[a[pos]].end()) ? 0 : (*ges);
    if (pre) Modify(pre, pos, pos - pre);
    if (suf) Modify(pos, suf, suf - pos);
    if (pre && suf) Modify(pre, suf, pre - suf);
  }
  return 0;
}
}  // namespace work
signed main() { return work::main(), IO::flush(), 0; }
