#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int SIZE = 3000;
const int CBRT = 35;
int arr[MAXN];
int lo[CBRT][CBRT], hi[CBRT][CBRT];
unordered_map<int, set<int>> state[CBRT][CBRT];
int sol[CBRT][CBRT];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  freopen("bla.out", "w", stdout);
  int n, m, i, j;
  int op, a, b;
  cin >> n >> m;
  for (i = 0; i < n; ++i) cin >> arr[i];
  while (m--) {
    cin >> op >> a >> b;
    --a;
    if (op == 1) {
      for (i = 0; i < CBRT; ++i)
        for (j = 0; j < CBRT; ++j)
          if (lo[i][j] <= a && a < hi[i][j]) {
            auto& st = state[i][j];
            sol[i][j] -= *prev(st[arr[a]].end()) - *st[arr[a]].begin();
            st[arr[a]].erase(a);
            if (st[arr[a]].size())
              sol[i][j] += *prev(st[arr[a]].end()) - *st[arr[a]].begin();
            if (st[b].size()) sol[i][j] -= *prev(st[b].end()) - *st[b].begin();
            st[b].insert(a);
            sol[i][j] += *prev(st[b].end()) - *st[b].begin();
          }
      arr[a] = b;
    } else {
      i = a / SIZE;
      j = b / SIZE;
      int& l = lo[i][j];
      int& r = hi[i][j];
      auto& st = state[i][j];
      while (l > a) {
        --l;
        if (st[arr[l]].size())
          sol[i][j] -= *prev(st[arr[l]].end()) - *st[arr[l]].begin();
        st[arr[l]].insert(l);
        sol[i][j] += *prev(st[arr[l]].end()) - *st[arr[l]].begin();
      }
      while (r < b) {
        if (st[arr[r]].size())
          sol[i][j] -= *prev(st[arr[r]].end()) - *st[arr[r]].begin();
        st[arr[r]].insert(r);
        sol[i][j] += *prev(st[arr[r]].end()) - *st[arr[r]].begin();
        ++r;
      }
      while (l < a) {
        sol[i][j] -= *prev(st[arr[l]].end()) - *st[arr[l]].begin();
        st[arr[l]].erase(l);
        if (st[arr[l]].size())
          sol[i][j] += *prev(st[arr[l]].end()) - *st[arr[l]].begin();
        ++l;
      }
      while (r > b) {
        --r;
        sol[i][j] -= *prev(st[arr[r]].end()) - *st[arr[r]].begin();
        st[arr[r]].erase(r);
        if (st[arr[r]].size())
          sol[i][j] += *prev(st[arr[r]].end()) - *st[arr[r]].begin();
      }
      cout << sol[i][j] << '\n';
    }
  }
}
