#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];
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);
}
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 || !j) return;
  for (; i <= n; i += i & -i) upd(ver[i], 1, n + 1, j, x);
}
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, i, j + 1); }
void del(int i) {
  int v = a[i];
  auto it = p[v].upper_bound(i);
  int l = 0, r = 0;
  if (it != p[v].end()) r = *it;
  it = prev(it);
  if (it != p[v].begin()) l = *prev(it);
  upd(r, l, r - l);
  upd(r, i, -(r - i));
  upd(i, l, -(i - l));
  p[v].erase(it);
}
void ins(int i, int v) {
  auto it = p[v].upper_bound(i);
  int l = 0, r = 0;
  if (it != p[v].end()) r = *it;
  if (it != p[v].begin()) l = *prev(it);
  upd(r, l, -(r - l));
  upd(r, i, r - i);
  upd(i, l, i - l);
  p[v].insert(it, i);
  a[i] = v;
}
int main() {
  int m;
  RD(n, m);
  for (int i(1); i < ((n) + 1); ++i) {
    int x;
    RD(x);
    ins(i, x);
  }
  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));
    }
  }
}
