#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 100;
const int INF = 1e5 + 10;
const int Bcksiz = 330;
const int MAXBckcnt = (MAXN + Bcksiz - 1) / Bcksiz;
set<int> W[MAXN];
int a[MAXN], C[MAXN], nxt[MAXN], lst[MAXN];
vector<pair<int, int> > V[MAXBckcnt];
int n;
int Bckcnt;
int fir(int p) { return p * Bcksiz + 1; }
int en(int p) { return min(n + 1, fir(p + 1)); }
int getB(int p) { return (p - 1) / Bcksiz; }
void changB(int f) {
  if (!f) {
    return;
  }
  int p = getB(f);
  V[p].clear();
  int Fi = fir(p), En = en(p);
  for (int i = Fi; i < En; i++) {
    V[p].push_back({nxt[i], i});
  }
  sort(V[p].begin(), V[p].end());
  C[Fi] = V[p][0].first - V[p][0].second;
  for (int i = Fi + 1; i < En; i++) {
    C[i] = C[i - 1] + V[p][i - Fi].first - V[p][i - Fi].second;
  }
}
void chang(int p, int x) {
  int f1 = lst[p], f2 = -1, f3 = -1;
  nxt[lst[p]] = nxt[p];
  lst[nxt[p]] = lst[p];
  W[a[p]].erase(p);
  set<int>::iterator it;
  it = W[x].upper_bound(p);
  int k = (*it);
  if (it == W[x].end()) {
    k = INF;
  }
  int k2;
  if (it == W[x].begin()) {
    k2 = 0;
  } else {
    it--;
    k2 = (*it);
  }
  f2 = p;
  f3 = k2;
  nxt[p] = k;
  lst[p] = k2;
  nxt[k2] = p;
  lst[k] = p;
  changB(f1);
  changB(f2);
  changB(f3);
  a[p] = x;
  W[x].insert(p);
}
int ask(int l, int r) {
  int p1 = getB(l) + 1;
  int p2 = getB(r);
  int ans = 0;
  for (int i = p1; i < p2; i++) {
    pair<int, int> k;
    k = {r, INF};
    int u = upper_bound(V[i].begin(), V[i].end(), k) - V[i].begin();
    u--;
    cout << l << ' ' << r << ' ' << i << ' ' << u << endl;
    for (int j = 0; j < V[i].size(); j++) {
    }
    if (u != -1) {
      ans += C[fir(i) + u];
    }
  }
  for (int i = l; i < min(r, fir(p1)); i++) {
    if (nxt[i] <= r) {
      ans += nxt[i] - i;
    }
  }
  for (int i = r; i >= max(l, fir(p2)); i--) {
    if (nxt[i] <= r) {
      ans += nxt[i] - i;
    }
  }
  if (p2 == p1 - 1) {
    return ans / 2;
  }
  return ans;
}
int main() {
  int q;
  cin >> n >> q;
  int A;
  Bckcnt = (n + Bcksiz - 1) / Bcksiz;
  for (int i = 0; i < n; i++) {
    nxt[i + 1] = i + 2;
    lst[i + 1] = i;
    W[0].insert(i + 1);
  }
  nxt[n] = INF;
  for (int i = 0; i < n; i++) {
    cin >> A;
    chang(i + 1, A);
  }
  int type = 0;
  int l, r;
  for (int i = 0; i < q; i++) {
    cin >> type;
    if (type == 1) {
      cin >> l >> r;
      chang(l, r);
    } else {
      cin >> l >> r;
      cout << ask(l, r) << endl;
    }
  }
}
