#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
const int M = 50 * N;
int n, m, a[N];
long long pool[M];
long long *f[N];
tuple<int, int, int> op[N];
set<pair<int, int> > S;
vector<int> V[N];
template <typename T>
void upd(T *c, int i, int v, int n) {
  while (i <= n) {
    c[i] += v;
    i += i & -i;
  }
}
template <typename T>
T qry(T *c, int i, int n) {
  T r = 0;
  while (i > 0) {
    r += c[i];
    i -= i & -i;
  }
  return r;
}
void add(int i, int v, int n) {
  while (i > 0) {
    V[i].push_back(v);
    i -= i & -i;
  }
}
void UPD(int i, pair<int, int> v, int n) {
  while (i <= n) {
    int p =
        lower_bound((V[i]).begin(), (V[i]).end(), v.first) - V[i].begin() + 1;
    upd(f[i], p, v.second, ((int)(V[i]).size()));
    i += i & -i;
  }
}
long long QRY(int i, int v, int n) {
  long long r = 0;
  while (i > 0) {
    int p = lower_bound((V[i]).begin(), (V[i]).end(), v) - V[i].begin() + 1;
    r += qry(f[i], p, ((int)(V[i]).size()));
    i -= i & -i;
  }
  return r;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = (1); i < (n + 1); ++i) {
    scanf("%d", a + i);
    S.insert(make_pair(a[i], i));
  }
  for (int i = (1); i < (n + 1); ++i)
    S.insert(make_pair(i, 0)), S.insert(make_pair(i, n + 1));
  for (int i = (0); i < (m); ++i) {
    int t, x, y;
    scanf("%d%d%d", &t, &x, &y);
    op[i] = make_tuple(t, x, y);
    if (t == 2) add(x - 1, x - 1, n), add(y, x - 1, n);
  }
  for (int i = (1); i < (n + 1); ++i) {
    V[i].push_back(n);
    sort((V[i]).begin(), (V[i]).end());
    V[i].erase(unique((V[i]).begin(), (V[i]).end()), V[i].end());
  }
  for (int i = 1, sum = 0; i <= n; ++i) {
    f[i] = pool + sum;
    sum += ((int)(V[i]).size());
  }
  for (int i = (1); i < (n + 1); ++i) {
    auto it = S.lower_bound(make_pair(a[i], i));
    int pre = (--it)->second;
    UPD(i, make_pair(pre, i - pre), n);
  }
  for (int i = (0); i < (m); ++i) {
    int t, x, y;
    tie(t, x, y) = op[i];
    if (t == 1) {
      auto it = S.lower_bound(make_pair(a[x], x));
      int pre = (--it)->second;
      int nxt = (++(++it))->second;
      S.erase(--it);
      UPD(x, make_pair(pre, -(x - pre)), n);
      UPD(nxt, make_pair(x, -(nxt - x)), n);
      UPD(nxt, make_pair(pre, nxt - pre), n);
      a[x] = y;
      S.insert(make_pair(a[x], x));
      it = S.lower_bound(make_pair(a[x], x));
      pre = (--it)->second;
      nxt = (++(++it))->second;
      UPD(nxt, make_pair(pre, -(nxt - pre)), n);
      UPD(nxt, make_pair(x, nxt - x), n);
      UPD(x, make_pair(pre, x - pre), n);
    } else {
      long long ans = QRY(y, n, n) - QRY(x - 1, n, n);
      ans -= QRY(y, x - 1, n) - QRY(x - 1, x - 1, n);
      printf("%lld\n", ans);
    }
  }
  return 0;
}
