#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 * 1000 + 17;
int a[MAXN], n, q;
map<int, long long> fen[MAXN];
set<int> s[MAXN];
pair<int, int> b[MAXN];
void add(int x, int y, int val) {
  for (; y <= n; y += y & (-y))
    for (int i = x; i <= n; i += i & (-i)) fen[y][i] += val;
}
long long get(int x, int y) {
  long long res = 0;
  for (; x; x -= x & (-x))
    for (int i = y; i; i -= i & (-i)) res += fen[x][i];
  return res;
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (s[a[i]].size())
      b[i].first = *s[a[i]].rbegin(), b[i].second = i - b[i].first,
      add(i, b[i].first, b[i].second);
    s[a[i]].insert(i);
  }
  int tmppp;
  while (q--) {
    int t, l, r;
    cin >> t >> l >> r;
    if (t == 1) {
      s[a[l]].erase(l);
      auto itr = s[a[l]].upper_bound(l);
      if (itr != s[a[l]].end()) {
        int tmp = *itr;
        if (itr != s[a[l]].begin()) {
          --itr;
          tmppp = -b[tmp].second;
          b[tmp] = {*itr, tmp - *itr};
          add(tmp, b[tmp].first, b[tmp].second + tmppp);
        } else {
          if (b[tmp].first) add(tmp, b[tmp].first, -b[tmp].second);
          b[tmp] = {0, 0};
        }
      }
      itr = s[r].upper_bound(l);
      if (itr != s[r].end()) {
        tmppp = -b[*itr].second;
        b[*itr] = {l, *itr - l};
        add(*itr, l, tmppp + *itr - l);
      }
      if (itr != s[r].begin()) {
        --itr;
        tmppp = -b[l].second;
        b[l] = {*itr, l - *itr};
        add(l, b[l].first, b[l].second);
      } else {
        if (b[l].first) add(l, b[l].first, -b[l].second);
        b[l] = {0, 0};
      }
      a[l] = r;
      s[r].insert(l);
    } else
      cout << get(r, r) - get(l - 1, r) << endl;
  }
  return 0;
}
