#include <bits/stdc++.h>
using namespace std;
template <class T>
void cmax(T& a, T b) {
  a = max(a, b);
}
template <class T>
void cmin(T& a, T b) {
  a = min(a, b);
}
void _BG(const char* s) {}
template <class T, class... TT>
void _BG(const char* s, T a, TT... b) {
  for (int c = 0; *s && (c || *s != ','); ++s) {
    cerr << *s;
    for (char x : "([{") c += *s == x;
    for (char x : ")]}") c -= *s == x;
  }
  cerr << " = " << a;
  if (*s) {
    cerr << ", ";
    _BG(++s, b...);
  } else
    cerr << endl;
}
bool RD() { return 1; }
bool RD(char& a) { return scanf(" %c", &a) == 1; }
bool RD(char* a) { return scanf("%s", a) == 1; }
bool RD(double& a) { return scanf("%lf", &a) == 1; }
bool RD(int& a) { return scanf("%d", &a) == 1; }
bool RD(long long& a) { return scanf("%lld", &a) == 1; }
template <class T, class... TT>
bool RD(T& a, TT&... b) {
  return RD(a) && RD(b...);
}
void PT(const char& a) { putchar(a); }
void PT(char const* const& a) { fputs(a, stdout); }
void PT(const double& a) { printf("%.16f", a); }
void PT(const int& a) { printf("%d", a); }
void PT(const long long& a) { printf("%lld", a); }
template <char s = ' ', char e = '\n'>
void PL() {
  if (e) PT(e);
}
template <char s = ' ', char e = '\n', class T, class... TT>
void PL(const T& a, const TT&... b) {
  PT(a);
  if (sizeof...(b) && s) PT(s);
  PL<s, e>(b...);
}
const int N = 1e5 + 87;
int n, a[N];
set<int> p[N];
long long f[N], c[N];
struct node {
  long long s;
  node *lc, *rc;
} * ver[N];
void upd(node*& t, int l, int r, int i, int x) {
  if (!t) t = new node();
  t->s += x;
  if (r - l == 1) return;
  int m = l + (r - l) / 2;
  if (i < m)
    upd(t->lc, l, m, i, x);
  else
    upd(t->rc, m, r, i, x);
  if (!t->s) {
    delete t;
    t = nullptr;
  }
}
long long qry(node* t, int l, int r, int i, int j) {
  if (!t || r <= i || j <= l) return 0;
  if (i <= l && r <= j) return t->s;
  int m = (l + r) / 2;
  return qry(t->lc, l, m, i, j) + qry(t->rc, m, r, i, j);
}
void upd(int i, int j, int x) {
  if (i < 1 || i > n || j < 1 || j > n) return;
  for (; i <= n; i += i & -i) upd(ver[i], 1, n + 1, j, x);
}
void add(int i, int x) {
  for (; i <= n; i += i & -i) f[i] += x;
}
void asn(int i, int x) {
  if (i < 1 || i > n) return;
  add(i, x - c[i]);
  upd(i, i, x - c[i]);
  c[i] = x;
}
long long qry(int i) {
  long long r = 0;
  for (; i; i ^= i & -i) r += f[i];
  return r;
}
long long qry(int i, int l, int r) {
  long long x = 0;
  for (; i; i ^= i & -i) x += qry(ver[i], 1, n + 1, l, r);
  return x;
}
long long qry(int i, int j) { return qry(j) - qry(i - 1) - qry(j, i, j + 1); }
void del(int i) {
  int v = a[i];
  auto it = p[v].upper_bound(i);
  int r = *it;
  it = prev(it);
  int l = *prev(it);
  p[v].erase(it);
  upd(i, l, c[l]);
  upd(r, i, c[i]);
  asn(l, r != n + 1 ? r - l : 0);
  upd(r, l, -c[l]);
}
void ins(int i, int v) {
  auto it = p[v].upper_bound(i);
  int l = *prev(it), r = *it;
  upd(r, l, c[l]);
  asn(l, i - l);
  upd(i, l, -c[l]);
  asn(i, r != n + 1 ? r - i : 0);
  upd(r, i, -c[i]);
  p[v].insert(it, i);
  a[i] = v;
}
int main() {
  int m;
  RD(n, m);
  for (int i(1); i < ((n) + 1); ++i) p[i] = {0, n + 1};
  for (int i(1); i < ((n) + 1); ++i) {
    RD(a[i]);
    ins(i, a[i]);
  }
  for (int __i(0); __i < (m); ++__i) {
    int t, x, y;
    RD(t, x, y);
    if (t == 1) {
      if (a[x] == y) continue;
      del(x);
      ins(x, y);
    } else {
      PL(qry(x, y));
    }
  }
}
