#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 5;
constexpr int BLOCK_SIZE = 200;
vector<pair<int, int> > ord[MAX];
vector<int> pref[MAX];
set<int> pos[MAX];
int arr[MAX], last[MAX], prv[MAX], nxt[MAX], block[MAX], block_start[MAX],
    b_end[MAX];
int aux[MAX];
int n;
long long bit[MAX];
void update(int idx, int val) {
  while (idx < MAX) {
    bit[idx] += val;
    idx += idx & -idx;
  }
}
long long query(int idx) {
  long long sum = 0;
  while (idx) {
    sum += bit[idx];
    idx -= idx & -idx;
  }
  return sum;
}
void update_b(int id) {
  pref[id].clear();
  sort(ord[id].begin(), ord[id].end());
  int sum = 0;
  for (int i = int(0); i < int(ord[id].size()); i++) {
    if (ord[id][i].first != -1) {
      sum += ord[id][i].second - ord[id][i].first;
    }
    pref[id].push_back(sum);
  }
}
int main() {
  int m;
  scanf("%d %d", &n, &m);
  memset(block_start, -1, sizeof block_start);
  int last_block = -1;
  for (int i = int(1); i < int(n + 1); i++) {
    scanf("%d", arr + i);
    block[i] = i / BLOCK_SIZE;
    if (block_start[block[i]] == -1) {
      block_start[block[i]] = i;
    }
    b_end[block[i]] = i;
    last_block = block[i];
    pos[arr[i]].insert(i);
  }
  memset(last, -1, sizeof last);
  for (int i = int(1); i < int(n + 1); i++) {
    prv[i] = last[arr[i]];
    if (prv[i] != -1) {
      aux[i] = i - prv[i];
    }
    ord[block[i]].emplace_back(prv[i], i);
    last[arr[i]] = i;
  }
  for (int i = int(0); i < int(last_block + 1); i++) {
    update_b(i);
  }
  for (int i = int(1); i < int(n + 1); i++) {
    update(i, aux[i]);
  }
  for (int t = int(0); t < int(m); t++) {
    int type;
    scanf("%d", &type);
    if (type == 1) {
      int p, x;
      scanf("%d %d", &p, &x);
      int b = block[p];
      auto it = pos[arr[p]].upper_bound(p);
      if (it != pos[arr[p]].end()) {
        update(*it, -(*it - p));
        int block_it = block[*it];
        ord[block_it].erase(find(ord[block_it].begin(), ord[block_it].end(),
                                 pair<int, int>(prv[*it], *it)));
        auto sei_la = pos[arr[p]].lower_bound(p);
        if (sei_la != pos[arr[p]].begin()) {
          prv[*it] = *prev(sei_la);
        } else {
          prv[*it] = -1;
        }
        if (prv[*it] != -1) {
          update(*it, *it - prv[*it]);
        }
        ord[block_it].emplace_back(prv[*it], *it);
        update_b(block_it);
      }
      if (prv[p] != -1) {
        update(p, -(p - prv[p]));
      }
      ord[b].erase(
          find(ord[b].begin(), ord[b].end(), pair<int, int>(prv[p], p)));
      pos[arr[p]].erase(p);
      arr[p] = x;
      auto other = pos[arr[p]].lower_bound(p);
      if (other != pos[arr[p]].end()) {
        if (other != pos[arr[p]].begin()) {
          auto pit = prev(other);
          update(*other, -(*other - *pit));
        }
        int ob = block[*other];
        ord[ob].erase(find(ord[ob].begin(), ord[ob].end(),
                           pair<int, int>(prv[*other], *other)));
        prv[*other] = p;
        ord[ob].emplace_back(prv[*other], *other);
        update_b(ob);
        update(*other, *other - p);
      }
      if (other != pos[arr[p]].begin()) {
        prv[p] = *prev(other);
      } else {
        prv[p] = -1;
      }
      if (prv[p] != -1) {
        update(p, p - prv[p]);
      }
      ord[b].emplace_back(prv[p], p);
      update_b(b);
      pos[arr[p]].insert(p);
    } else {
      int l, r;
      scanf("%d %d", &l, &r);
      long long ans = query(r) - query(l - 1);
      long long to_rem = 0;
      if (block[l] == block[r]) {
        for (auto &each : ord[block[l]]) {
          if (each.second >= l && each.second <= r) {
            if (each.first < l && each.first != -1) {
              to_rem += each.second - each.first;
            }
          }
        }
      } else {
        for (auto &each : ord[block[l]]) {
          if (each.second >= l && each.second <= r) {
            if (each.first < l && each.first != -1) {
              to_rem += each.second - each.first;
            }
          }
        }
        for (int i = int(block[l] + 1); i < int(block[r]); i++) {
          int before =
              lower_bound(ord[i].begin(), ord[i].end(), pair<int, int>(l, 0)) -
              ord[i].begin();
          to_rem += before > 0 ? pref[i][before - 1] : 0;
        }
        for (auto &each : ord[block[r]]) {
          if (each.second >= l && each.second <= r) {
            if (each.first < l && each.first != -1) {
              to_rem += each.second - each.first;
            }
          }
        }
      }
      ans -= to_rem;
      printf("%lld\n", ans);
    }
  }
  return 0;
}
