#include <bits/stdc++.h>
using namespace std;
int n, q;
map<int, long long> ft[100005];
set<int> sets[100005];
pair<int, int> val[100005];
void add(int x, int y, int val) {
  for (; x <= n; x += x & -x) {
    for (int j = y; j <= n; j += j & -j) {
      ft[x][j] += val;
    }
  }
}
long long sum(int x, int y) {
  long long ans = 0;
  for (; x > 0; x -= x & -x) {
    for (int j = y; j > 0; j -= j & -j) {
      if (ft[x].count(j)) ans += ft[x][j];
    }
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> q;
  vector<int> arr(n + 1);
  for (long long i = 1; i < n + 1; i++) {
    cin >> arr[i];
    if (!sets[arr[i]].empty()) {
      val[i].first = *sets[arr[i]].rbegin();
      val[i].second = i - val[i].first;
      add(val[i].first, i, val[i].second);
    }
    sets[arr[i]].insert(i);
  }
  while (q--) {
    int qt, l, r;
    cin >> qt >> l >> r;
    if (qt == 2)
      cout << sum(r, r) - sum(l - 1, r) << '\n';
    else {
      sets[arr[l]].erase(l);
      auto it = sets[arr[l]].upper_bound(l);
      if (val[l].first) {
        add(val[l].first, l, -val[l].second);
      }
      if (it != sets[arr[l]].end()) {
        add(val[*it].first, *it, -val[*it].second);
        auto temp = it;
        if (it != sets[arr[l]].begin()) {
          --it;
          val[*temp] = {*it, *temp - *it};
          add(val[*temp].first, *temp, val[*temp].second);
        } else {
          val[*temp] = {0, 0};
        }
      }
      it = sets[r].upper_bound(l);
      if (it != sets[r].end()) {
        if (val[*it].first) add(val[*it].first, *it, -val[*it].second);
        val[*it] = {l, *it - l};
        add(val[*it].first, *it, val[*it].second);
      }
      if (it != sets[r].begin()) {
        --it;
        val[l] = {*it, l - *it};
        add(val[l].first, l, val[l].second);
      } else {
        val[l] = {0, 0};
      }
      arr[l] = r;
      sets[r].insert(l);
    }
  }
  return 0;
}
